109972024-06-01 16:46:25szilGeometric Meancpp17Accepted 100/100527ms30352 KiB
#include <bits/stdc++.h>
#include <iterator>

using ll = long long;
using namespace std;

const int MAXN = 1'000'001;
const ll INF = 1e12 + 1;

int szita[MAXN];

void solve() {
    int n;
    cin >> n;
    vector<ll> v(n + 1);
    vector<vector<int> > p(n + 1);
    unordered_map<ll, int> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i];
        int x = v[i];
        while(x != 1)
        {
            p[i].push_back(szita[x]);
            x /= szita[x];
        }
    }
    ll ans = 0;
    vector<vector<ll> > ins(n + 2);
    for(int i = 1; i <= n; i++)
    {
        for(auto x : ins[i]) m[x]++;
        for(int j = i + 1; j <= n; j++) {
            vector<int> pt;
            merge(p[i].begin(), p[i].end(), p[j].begin(), p[j].end(), back_inserter(pt));
            pt.push_back(1);
            ll w = 1;
            ll la = 1, db = 0;
            ll mul = v[i] * v[j];
            for(auto x : pt)
            {
                if(x == la)
                {
                    db++;
                }
                if(x != la)
                {
                    ll m = 1;
                    while(db >= 4)
                    {
                        for(int i = 0; i < 4; i++) mul /= la;
                        db -= 4;
                    }
                    int z = (4 - db) % 4;
                    for(int i = 0; i < z; i++)
                    {
                        if(w == -1) continue;
                        w *= la;
                        if(w > INF) w = -1;
                    }
                    db = 1;
                }
                la = x;
            }
            ans += m[w];
            ins[j + 1].push_back(mul);
        }
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (int i = 2; i < MAXN; i++) {
        if (!szita[i]) {
            szita[i] = i;
            for (int j = 2*i; j < MAXN; j += i) {
                if (!szita[j]) szita[j] = i;
            }
        }
    }
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted17ms4324 KiB
2Accepted14ms4324 KiB
3Accepted17ms4324 KiB
subtask210/10
4Accepted17ms4240 KiB
5Accepted17ms4324 KiB
6Accepted16ms4328 KiB
7Accepted17ms4452 KiB
8Accepted17ms4324 KiB
9Accepted17ms4324 KiB
10Accepted17ms4196 KiB
11Accepted17ms4452 KiB
12Accepted16ms4196 KiB
13Accepted16ms4256 KiB
14Accepted14ms4488 KiB
15Accepted16ms4456 KiB
16Accepted16ms4480 KiB
17Accepted16ms4452 KiB
18Accepted16ms4584 KiB
subtask310/10
19Accepted17ms4240 KiB
20Accepted17ms4324 KiB
21Accepted16ms4328 KiB
22Accepted17ms4452 KiB
23Accepted17ms4324 KiB
24Accepted17ms4324 KiB
25Accepted17ms4196 KiB
26Accepted17ms4452 KiB
27Accepted16ms4196 KiB
28Accepted16ms4256 KiB
29Accepted14ms4488 KiB
30Accepted16ms4456 KiB
31Accepted16ms4480 KiB
32Accepted16ms4452 KiB
33Accepted16ms4584 KiB
34Accepted16ms4388 KiB
35Accepted16ms4228 KiB
36Accepted17ms4472 KiB
37Accepted17ms4324 KiB
38Accepted14ms4252 KiB
39Accepted17ms4252 KiB
40Accepted17ms4452 KiB
41Accepted16ms4344 KiB
42Accepted17ms4252 KiB
43Accepted16ms4344 KiB
44Accepted16ms4324 KiB
45Accepted17ms4472 KiB
subtask410/10
46Accepted18ms4284 KiB
47Accepted98ms5580 KiB
48Accepted208ms7680 KiB
49Accepted337ms9764 KiB
50Accepted342ms9828 KiB
51Accepted347ms9700 KiB
52Accepted351ms9828 KiB
53Accepted361ms9828 KiB
54Accepted342ms9700 KiB
subtask525/25
55Accepted17ms4240 KiB
56Accepted17ms4324 KiB
57Accepted16ms4328 KiB
58Accepted17ms4452 KiB
59Accepted17ms4324 KiB
60Accepted17ms4324 KiB
61Accepted17ms4196 KiB
62Accepted17ms4452 KiB
63Accepted16ms4196 KiB
64Accepted16ms4256 KiB
65Accepted14ms4488 KiB
66Accepted16ms4456 KiB
67Accepted16ms4480 KiB
68Accepted16ms4452 KiB
69Accepted16ms4584 KiB
70Accepted16ms4388 KiB
71Accepted16ms4228 KiB
72Accepted17ms4472 KiB
73Accepted17ms4324 KiB
74Accepted14ms4252 KiB
75Accepted17ms4252 KiB
76Accepted17ms4452 KiB
77Accepted16ms4344 KiB
78Accepted17ms4252 KiB
79Accepted16ms4344 KiB
80Accepted16ms4324 KiB
81Accepted17ms4472 KiB
82Accepted25ms5220 KiB
83Accepted23ms4744 KiB
84Accepted30ms4624 KiB
85Accepted35ms4660 KiB
86Accepted23ms4580 KiB
87Accepted28ms4532 KiB
88Accepted28ms4580 KiB
89Accepted18ms4580 KiB
90Accepted32ms4560 KiB
91Accepted32ms5268 KiB
92Accepted27ms5224 KiB
93Accepted27ms5260 KiB
94Accepted27ms5420 KiB
95Accepted27ms5216 KiB
96Accepted26ms5220 KiB
subtask645/45
97Accepted17ms4240 KiB
98Accepted17ms4324 KiB
99Accepted16ms4328 KiB
100Accepted17ms4452 KiB
101Accepted17ms4324 KiB
102Accepted17ms4324 KiB
103Accepted17ms4196 KiB
104Accepted17ms4452 KiB
105Accepted16ms4196 KiB
106Accepted16ms4256 KiB
107Accepted14ms4488 KiB
108Accepted16ms4456 KiB
109Accepted16ms4480 KiB
110Accepted16ms4452 KiB
111Accepted16ms4584 KiB
112Accepted16ms4388 KiB
113Accepted16ms4228 KiB
114Accepted17ms4472 KiB
115Accepted17ms4324 KiB
116Accepted14ms4252 KiB
117Accepted17ms4252 KiB
118Accepted17ms4452 KiB
119Accepted16ms4344 KiB
120Accepted17ms4252 KiB
121Accepted16ms4344 KiB
122Accepted16ms4324 KiB
123Accepted17ms4472 KiB
124Accepted18ms4284 KiB
125Accepted98ms5580 KiB
126Accepted208ms7680 KiB
127Accepted337ms9764 KiB
128Accepted342ms9828 KiB
129Accepted347ms9700 KiB
130Accepted351ms9828 KiB
131Accepted361ms9828 KiB
132Accepted342ms9700 KiB
133Accepted25ms5220 KiB
134Accepted23ms4744 KiB
135Accepted30ms4624 KiB
136Accepted35ms4660 KiB
137Accepted23ms4580 KiB
138Accepted28ms4532 KiB
139Accepted28ms4580 KiB
140Accepted18ms4580 KiB
141Accepted32ms4560 KiB
142Accepted32ms5268 KiB
143Accepted27ms5224 KiB
144Accepted27ms5260 KiB
145Accepted27ms5420 KiB
146Accepted27ms5216 KiB
147Accepted26ms5220 KiB
148Accepted389ms30352 KiB
149Accepted172ms10128 KiB
150Accepted412ms9820 KiB
151Accepted527ms9828 KiB
152Accepted137ms9700 KiB
153Accepted347ms9744 KiB
154Accepted342ms9796 KiB
155Accepted104ms9672 KiB
156Accepted368ms9828 KiB
157Accepted361ms11328 KiB
158Accepted328ms22536 KiB
159Accepted386ms28984 KiB
160Accepted442ms30160 KiB
161Accepted393ms29104 KiB
162Accepted453ms29260 KiB
163Accepted305ms9828 KiB
164Accepted273ms21432 KiB