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$。