题意：给定一个长度为 \(n\) 的序列，求最少能将这个序列分成多少段使得任意一段中不存在两个数的积为完全平方数。
一个小 Trick：如果两个数乘起来为平方数，可以先将每个数的平方因子除掉，然后这两个数必然相等。于是这道题被转化为了一个区间不能有相等的值，这就很典了。
设 \(pos_{a_{i}}\) 表示上一个 \(a_{i}\) 出现在哪里（也就是最远可以满足条件的位置），那么有 dp 转移方程 \(dp_{i}=dp_{pos_{a_{i}}}+1\)，时间复杂度 \(O(n)\)。
注意分解质因数的时候可以先将质数线性筛出来，这样效率更高。
代码是 E2 的，于是在这里就不贴了，评测记录。
标签：division,平方,Square,题解,pos,version,easy,dp From： https://www.cnblogs.com/Creeperl/p/17913391.html