传送门：>Here<
题目大意：先抛出了一个问题——“已知一个序列，将此序列中的元素划分成几组（不需要连续）使得每一组中的任意两个数的乘积都是完全平方数。特殊的，一个数可以为一组。先要求最少分几组。”在这个问题的基础上，给出一个长度为n的序列$a_i$，该序列有\(\frac{n(n+1)}{2}\)个子串，求每个子串对于上面这个问题最少划分几次。并分别统计最少划分k次的子串有几个。$(n \leq 5000, |a_i| \leq 10^8)$
解题思路
两个数的乘积为完全平方数，当且仅当两个数都为完全平方数，或者两个数相等。我们考虑放宽一下要求，如果只要求两个数相等，那么题目就变成求区间颜色个数的经典问题了。我们发现，如果我们将每个数的完全平方因子除去，那么所有完全平方数都变成1了，然而并不会影响答案。这样就只剩下两数相等的条件了。
求解所有区间的颜色个数和——常规做法是只让首次出现的颜色产生贡献。这需要我们统计每个数之前出现的相同数的位置。
关于除掉完全平方因子，注意要从大到小除。
Code
/*By QiXingzhi*/
#include <cstdio>
#include <cmath>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int N = ;
const int INF = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar();
return x * w;
}
int n,m;
int a[N],ans[N],f[N];
inline int GetNotSquare(int x){
int k = ceil(sqrt(abs(x)));
for(int i = ; i <= k; ++i){
while(x % (i*i) == ){
x /= i*i;
}
}
return x;
}
int main(){
n = r;
for(int i = ; i <= n; ++i){
a[i] = r;
a[i] = GetNotSquare(a[i]);
}
f[] = -;
for(int i = ; i <= n; ++i){
f[i] = -;
for(int j = i-; j >= ; --j){
if(a[i] == a[j]){
f[i] = j;
break;
}
}
}
for(int i = ; i <= n; ++i){
int num = ;
for(int j = i; j <= n; ++j){
if(f[j] < i && a[j] != ){
++num;
}
if(num == ){
++ans[];
}
else ++ans[num];
}
}
for(int i = ; i <= n; ++i) printf("%d ",ans[i]);
return ;
}