无平方因子划分（困难版）题解

思路

把一个正整数质因数分解，并只保留指数为奇数的质因子之积，称为它的无平方因子核。两个数的乘积为完全平方数，当且仅当它们的无平方因子核相同。因此，原条件等价于每一段内的核互不相同。

若某段内某个核出现 $c$ 次，那么保留其中一个、修改其余 $c-1$ 个即可。于是该段所需的最少修改次数正是

$$\sum_x\max(0,c_x-1),$$

也就是扫描该段时遇到的重复出现次数。

小规模子任务可以枚举 $n-1$ 个相邻位置是否切开，并计算所有段的重复代价。中规模子任务可以枚举最后一段的左端点，做 $O(n^2k)$ 动态规划。

满分做法利用 $k\le20$。对每个修改预算 $b\in[0,k]$，用双指针预处理 $L_{b,r}$：它是使区间 $[L_{b,r},r]$ 的重复次数不超过 $b$ 的最小左端点。

做法

设 $dp_{i,j}$ 表示只考虑前 $i$ 个数、至多使用 $j$ 次修改时的最少段数。最后一段若使用 $b$ 次修改，就可以尽量向左延伸到 $L_{b,i}$，转移为

$$dp_{i,j}=\min_{0\le b\le j}\left(dp_{L_{b,i-1},j-b}+1\right).$$

初值为 $dp_{0,j}=0$。双指针预处理时维护窗口内各核出现次数以及重复次数；加入一个已出现过的核会令重复次数加一，移走一个仍有剩余副本的核会令重复次数减一。

为了避免值域带来的常数问题，先计算所有数的无平方因子核，再将这些核离散化。不同测试中相同原数的核可以缓存。

复杂度

设一个输入文件中所有测试用例的长度之和为 $N$。核分解之外，双指针预处理为 $O(Nk)$，动态规划为 $O(Nk^2)$，空间复杂度为 $O(Nk)$。由于 $k\le20$，可以通过本题限制。