hyz's blog
0%

CF 980D: Perfect Groups

发表于

题意

给一个数组，让你给这个数组分组，使得组内的元素两两相乘都是平方数，记最少分组数为d。

现在给你一个数组a，求出它所有连续子序列的d，然后输出每个d(1<= d <= n)的计数。

分析

用唯一分解定理分解平方数，可以发现它的某一素因子的个数为偶数个。若两个数相乘是平方数，则两者的所有素因子中，要么两个数都具有偶数个，要么都具有奇数个。因此，我们可以将一个数表示成它那些奇数个数的素因子的乘积。然后，若两个数相同，则可以组成平方数，否则不可以。于是，问题就转化成了求连续子序列中出现不同数字的个数，容易想到用set来维护，但是由于我们需要用$ O(n^{2}) $的时间来枚举连续子序列的起点和终点，再用上个set会超时。所以，结合数组a的元素很大，我们需要将其离散化，然后用一个桶来维护。

代码

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

vi pri;
int n, a[N], ans[N];

void pre() {
    int up = 10000;
    bool vis[N];
    memset(vis, 0, sizeof vis);
    for(int i = 2; i <= up; i++)
        if(!vis[i])
            for(int j = 2 * i; j <= up; j += i)
                vis[j] = 1;
    for(int i = 2; i <= up; i++)
        if(!vis[i])
            pri.push_back(i);
}

int fac(int d) {
    if(d == 0) return d;
    int ans = 1;
    if(d < 0) ans *= -1, d *= -1;
    int p = 0;
    while(d != 1 && p < pri.size()) {
        int cnt = 0;
        while(d % pri[p] == 0)
            cnt++, d /= pri[p];
        if(cnt & 1)
            ans *= pri[p];
        p++;
    }
    if(d != 1)
        ans *= d;

    return ans;
}

void lisanhua() {
    set<int> se;
    map<int, int> m;
    for(int i = 0; i < n; i++)
        se.insert(a[i]);
    int cnt = 1;
    for(auto i: se) {
        if(i == 0)
            m[i] = 0;
        else
            m[i] = cnt++;
    }
    for(int i = 0; i < n; i++)
        a[i] = m[a[i]];
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    pre();
    while(cin >> n) {
        for(int i = 0; i < n; i++) {
            scanf("%d", a + i);
            a[i] = fac(a[i]);
        }
        memset(ans, 0, sizeof ans);
        lisanhua();
        for(int i = 0; i < n; i++) {
            int cnt = 0, zeroFlag = 0, b[N];
            memset(b, 0, sizeof b);
            for(int j = i; j < n; j++) {
                if(a[j] == 0)
                    zeroFlag = 1;
                if(b[a[j]]++ == 0)
                    cnt++;
                if(zeroFlag && cnt != 1)
                    ans[cnt-1]++;
                else
                    ans[cnt]++;
            }
        }
        for(int i = 1; i <= n; i++)
            printf("%d%c", ans[i], i == n ? '\n': ' ');
    }

    return 0;
}