题意
定义一个串的权值是将其划分成 (k) 组，使得每一组在满足“从组里选出一个数，再从组里选出一个数，它们的乘积没有平方因子”这样的前提时的最小的 (k)。每组的数不必相邻， 不必连续。
现在给你一串数，问你，权值为 (1,2,ldots,n) 的子串分别有多少个。
解答
显然如果一个数中含有平方因子，抹去平方因子也不会对答案产生影响。
因此对于一个串，抹去平方因子后，有多少种不同的数，权值就是多少。注意要特判 (0)。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
int n, a[5005], cnt, b[5005], ans[5005];
map<int,int> mp;
bool vis[5005];
int f(int x){
if(x>=-1 && x<=1) return x;
int flg=1;
if(x<0){
flg = -1;
x *= -1;
}
for(int i=2; i<=10000; i++){
if(i*i>x) break;
while(x%(i*i)==0)
x /= i * i;
}
return x*flg;
}
int main(){
cin>>n;
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
a[i] = f(a[i]);
if(!mp[a[i]]){
mp[a[i]] = ++cnt;
b[i] = cnt;
}
else b[i] = mp[a[i]];
}
for(int i=1; i<=n; i++){
cnt = 0;
memset(vis, 0, sizeof(vis));
for(int j=i; j<=n; j++){
if(a[j]==0){
if(!cnt) ans[1]++;
else ans[cnt]++;
}
else{
if(!vis[b[j]]){
vis[b[j]] = true;
cnt++;
}
ans[cnt]++;
}
}
}
for(int i=1; i<=n; i++)
printf("%d ", ans[i]);
return 0;
}