Submission #1533358

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;

#define OUT(x)  cerr << #x << " = " << x << endl;
#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define pll     pair<long long, long long>
#define ll      long long

//V以下の素数列挙。O(V log log V)
int V = 2180; //V * V * V >= 10^10
vector<int> prime;
void init() {
        vector<bool> is_prime(V + 1, true);
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i <= V; i ++) {
                if (is_prime[i]) {
                        prime.push_back(i);
                        for (int j = i + i; j <= V; j += i) is_prime[j] = false;
                }
        }
}

int main() {
        init();
        int n;
        cin >> n;
        vector<ll> a(n);
        for (int i = 0; i < n; i ++) cin >> a[i];
        unordered_map<ll, pll> cnts; //その数字の個数と、その数字のペア的なやつの数
        for (auto v : a) {
                ll val = 1, another = 1;
                for (auto p : prime) {
                        if (v % p != 0) continue;
                        int cnt = 0;
                        while (v % p == 0) {
                                cnt ++;
                                v /= p;
                        }
                        cnt %= 3;
                        if (cnt == 1) {
                                val *= p;
                                another *= p * p;
                        } else if (cnt == 2) {
                                val *= p * p;
                                another *= p;
                        }
                }
                if (v > 1) {
                        ll tmp = sqrt(v);
                        ll root = 0;
                        for (int i = -1; i < 2; i ++) if ((tmp + i) * (tmp + i) == v) root = tmp + i;
                        if (root) {
                                val *= v;
                                another *= root;
                        } else {
                                val *= v;
                                another = v * v;
                        }
                }
                cnts[val].second = another;
                cnts[val].first ++;
        }
        auto tmp = cnts;
        ll ans = 0;
        for (auto u : tmp) if (u.first != 1 && cnts[u.second.second] < u.second) ans += u.second.first;
        if (cnts[1].first != 0) ans ++;
        cout << ans << endl;
        return 0;
}

Submission Info

Judge Result