题目大意,给定一个序列,定义一个区间的答案是 $[L,R]$ 的数最少被分成几组满足每组内任意数两两之积为完全平方数,对于每个 $k$ 输出答案为 $k$ 的区间数

两个数能成完全平方数,对应他们的积的每个幂次都是偶数,并且不难发现,如果他们的幂次都是奇数的话,他们还可以和其他幂次为奇数且满足上面的条件的组合,这启发我们寻找一个 $\text{trick} $ 即这些素数每个幂次在模 $2$ 意义下相同(即每个数相等),就可以在一个区间,如果一个数本身就是完全平方数,它能和 $1$ 在一组 ,对于特殊的 $0$ ,由于能和任意的数在一组,因此需要特殊判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

typedef long long ll;

namespace mstd{

//change it if ll

inline void qread(int &x)
{
int f=1; x=0; static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=f; return ;
}

}

const int maxn=5100;

int n,m,a[maxn],b[maxn];
int ans[maxn],c[maxn];

inline void solve()
{
int i,j;
for(i=1;i<=n;i++)
{
int aans=0;
memset(c,0,sizeof(c));
for(j=i;j<=n;j++)
{
if(!c[a[j]]&&b[a[j]]!=0) c[a[j]]++,aans++;
if(!aans) ans[1]++;
else ans[aans]++;
}
}
for(i=1;i<=n;i++) printf("%d ",ans[i]);
return ;
}

int main()
{
int i,j;
mstd::qread(n);
for(i=1;i<=n;i++)
{
mstd::qread(a[i]);
int tmp=abs(a[i]);
for(j=2;j*j<=abs(a[i]);j++)
{
while(tmp%(j*j)==0) tmp/=j*j;
}
if(a[i]<0) a[i]=-tmp; else a[i]=tmp;
b[i]=a[i];
}
sort(b+1,b+n+1);
int tot=unique(b+1,b+n+1)-b-1;
for(i=1;i<=n;i++) a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
solve();
return 0;
}