题目描述
Solution
注意到两个数如果相乘是完全平方数，那么这两个数只留下质数次幂为奇数的质数之后一定是一样的
注意到能分到一组中的数一定在留下质数次幂为奇数的质数后是一样的
那么我们对于每个区间数数字个数即可
注意 $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
| #include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 5010
using namespace std;
int n, a[maxn];
vector<int> b;
int ans[maxn], cnt[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
for (int j = 2; j * j <= abs(a[i]); ++j)
while (a[i] % (j * j) == 0) a[i] /= j * j;
b.push_back(a[i]);
}
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (int i = 1; i <= n; ++i) a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
for (int i = 1; i <= n; ++i) {
fill(cnt, cnt + n, 0);
for (int j = i, s = 0; j <= n; ++j) {
if (++cnt[a[j]] == 1 && b[a[j]]) ++s;
++ans[max(1, s)];
}
}
for (int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n];
return 0;
}
|