109972024-06-01 16:46:25szilGeometric Meancpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva17ms4324 KiB
2Elfogadva14ms4324 KiB
3Elfogadva17ms4324 KiB
subtask210/10
4Elfogadva17ms4240 KiB
5Elfogadva17ms4324 KiB
6Elfogadva16ms4328 KiB
7Elfogadva17ms4452 KiB
8Elfogadva17ms4324 KiB
9Elfogadva17ms4324 KiB
10Elfogadva17ms4196 KiB
11Elfogadva17ms4452 KiB
12Elfogadva16ms4196 KiB
13Elfogadva16ms4256 KiB
14Elfogadva14ms4488 KiB
15Elfogadva16ms4456 KiB
16Elfogadva16ms4480 KiB
17Elfogadva16ms4452 KiB
18Elfogadva16ms4584 KiB
subtask310/10
19Elfogadva17ms4240 KiB
20Elfogadva17ms4324 KiB
21Elfogadva16ms4328 KiB
22Elfogadva17ms4452 KiB
23Elfogadva17ms4324 KiB
24Elfogadva17ms4324 KiB
25Elfogadva17ms4196 KiB
26Elfogadva17ms4452 KiB
27Elfogadva16ms4196 KiB
28Elfogadva16ms4256 KiB
29Elfogadva14ms4488 KiB
30Elfogadva16ms4456 KiB
31Elfogadva16ms4480 KiB
32Elfogadva16ms4452 KiB
33Elfogadva16ms4584 KiB
34Elfogadva16ms4388 KiB
35Elfogadva16ms4228 KiB
36Elfogadva17ms4472 KiB
37Elfogadva17ms4324 KiB
38Elfogadva14ms4252 KiB
39Elfogadva17ms4252 KiB
40Elfogadva17ms4452 KiB
41Elfogadva16ms4344 KiB
42Elfogadva17ms4252 KiB
43Elfogadva16ms4344 KiB
44Elfogadva16ms4324 KiB
45Elfogadva17ms4472 KiB
subtask410/10
46Elfogadva18ms4284 KiB
47Elfogadva98ms5580 KiB
48Elfogadva208ms7680 KiB
49Elfogadva337ms9764 KiB
50Elfogadva342ms9828 KiB
51Elfogadva347ms9700 KiB
52Elfogadva351ms9828 KiB
53Elfogadva361ms9828 KiB
54Elfogadva342ms9700 KiB
subtask525/25
55Elfogadva17ms4240 KiB
56Elfogadva17ms4324 KiB
57Elfogadva16ms4328 KiB
58Elfogadva17ms4452 KiB
59Elfogadva17ms4324 KiB
60Elfogadva17ms4324 KiB
61Elfogadva17ms4196 KiB
62Elfogadva17ms4452 KiB
63Elfogadva16ms4196 KiB
64Elfogadva16ms4256 KiB
65Elfogadva14ms4488 KiB
66Elfogadva16ms4456 KiB
67Elfogadva16ms4480 KiB
68Elfogadva16ms4452 KiB
69Elfogadva16ms4584 KiB
70Elfogadva16ms4388 KiB
71Elfogadva16ms4228 KiB
72Elfogadva17ms4472 KiB
73Elfogadva17ms4324 KiB
74Elfogadva14ms4252 KiB
75Elfogadva17ms4252 KiB
76Elfogadva17ms4452 KiB
77Elfogadva16ms4344 KiB
78Elfogadva17ms4252 KiB
79Elfogadva16ms4344 KiB
80Elfogadva16ms4324 KiB
81Elfogadva17ms4472 KiB
82Elfogadva25ms5220 KiB
83Elfogadva23ms4744 KiB
84Elfogadva30ms4624 KiB
85Elfogadva35ms4660 KiB
86Elfogadva23ms4580 KiB
87Elfogadva28ms4532 KiB
88Elfogadva28ms4580 KiB
89Elfogadva18ms4580 KiB
90Elfogadva32ms4560 KiB
91Elfogadva32ms5268 KiB
92Elfogadva27ms5224 KiB
93Elfogadva27ms5260 KiB
94Elfogadva27ms5420 KiB
95Elfogadva27ms5216 KiB
96Elfogadva26ms5220 KiB
subtask645/45
97Elfogadva17ms4240 KiB
98Elfogadva17ms4324 KiB
99Elfogadva16ms4328 KiB
100Elfogadva17ms4452 KiB
101Elfogadva17ms4324 KiB
102Elfogadva17ms4324 KiB
103Elfogadva17ms4196 KiB
104Elfogadva17ms4452 KiB
105Elfogadva16ms4196 KiB
106Elfogadva16ms4256 KiB
107Elfogadva14ms4488 KiB
108Elfogadva16ms4456 KiB
109Elfogadva16ms4480 KiB
110Elfogadva16ms4452 KiB
111Elfogadva16ms4584 KiB
112Elfogadva16ms4388 KiB
113Elfogadva16ms4228 KiB
114Elfogadva17ms4472 KiB
115Elfogadva17ms4324 KiB
116Elfogadva14ms4252 KiB
117Elfogadva17ms4252 KiB
118Elfogadva17ms4452 KiB
119Elfogadva16ms4344 KiB
120Elfogadva17ms4252 KiB
121Elfogadva16ms4344 KiB
122Elfogadva16ms4324 KiB
123Elfogadva17ms4472 KiB
124Elfogadva18ms4284 KiB
125Elfogadva98ms5580 KiB
126Elfogadva208ms7680 KiB
127Elfogadva337ms9764 KiB
128Elfogadva342ms9828 KiB
129Elfogadva347ms9700 KiB
130Elfogadva351ms9828 KiB
131Elfogadva361ms9828 KiB
132Elfogadva342ms9700 KiB
133Elfogadva25ms5220 KiB
134Elfogadva23ms4744 KiB
135Elfogadva30ms4624 KiB
136Elfogadva35ms4660 KiB
137Elfogadva23ms4580 KiB
138Elfogadva28ms4532 KiB
139Elfogadva28ms4580 KiB
140Elfogadva18ms4580 KiB
141Elfogadva32ms4560 KiB
142Elfogadva32ms5268 KiB
143Elfogadva27ms5224 KiB
144Elfogadva27ms5260 KiB
145Elfogadva27ms5420 KiB
146Elfogadva27ms5216 KiB
147Elfogadva26ms5220 KiB
148Elfogadva389ms30352 KiB
149Elfogadva172ms10128 KiB
150Elfogadva412ms9820 KiB
151Elfogadva527ms9828 KiB
152Elfogadva137ms9700 KiB
153Elfogadva347ms9744 KiB
154Elfogadva342ms9796 KiB
155Elfogadva104ms9672 KiB
156Elfogadva368ms9828 KiB
157Elfogadva361ms11328 KiB
158Elfogadva328ms22536 KiB
159Elfogadva386ms28984 KiB
160Elfogadva442ms30160 KiB
161Elfogadva393ms29104 KiB
162Elfogadva453ms29260 KiB
163Elfogadva305ms9828 KiB
164Elfogadva273ms21432 KiB