Codeforces Round #717 Cut - 数论+二分+DP

题意

给你一个长度为$n$的数组$a$。问你在$[l, r]$区间内的数组最少要划分成多少个连续的子区间,使得子区间内的所有数的乘积等于其最小公倍数。


题解

首先,“所有数的乘积等于其最小公倍数”意味着这些数两两互质。两两互质意味着这些数中,任意两个数的素因数各不相同。

最朴素的做法:

从$l$出发,不断尝试向右扩展。假设当前尝试扩展$i_1$,那么检查是否对于所有的$j\in[l, i_1-1]$,都有$gcd(a_j,a_{i_1})=1$。

然后再从$i_1$出发,按照同样的方法寻找$i_2$、$i_3$,直到$r$。每次都是一个新的一段。

稍微优化一点的做法:

我们可以看到,上面的做法中,每次查询的复杂度是$O(n^2)$的。现在,我们将每次查询优化成$O(n)$的。

我们维护一个数组$last$,其中$last[i]$表示第$i$个素数最后一次出现的下标。再定义数组$next$,其中$next[pos]$表示第$pos$个数往右最远能扩展到的位置(不包含$next[pos]$)。

于是当我们对$a_x$进行质因数分解的时候,我们通过$last[i]$找到上一个有这个质因子的位置$pos$。于是显然有$gcd(a_x,a_{pos})\neq 1$。进而显然有$next[pos]=min(next[pos], x)$。

于是我们从$l$出发,每次跳到$next[l]$。直到跳到$r$。每跳一次都是新的一段。

最终做法:

虽然每次查询已经是$O(n)$的,但总共有$n$次查询,因此总体是$O(n^2)$的。我们要进一步优化成$O(n\cdot log(n))$。

定义$dp[i][j]$表示,从$j$出发,跳$2^i$次之后,能到达的位置。于是有:$$dp[i][j]=dp[i-1][dp[i-1][j]]$$

于是我们从$l$出发,二分找到最大的$i$,使得$dp[i][j]<r$。如此往复,直到找不到这样的$i$。


代码

Submission #113906247 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论