10 pts 求助 qaq

U326351，只过了小值域的点，剩下真调不出来了。救救孩子 /kk

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef __int128 lll;

const int MAXN = 1e5 + 10;
const int prime[] = { 2, 3, 5, 7, 11, 61, 24251 };

mt19937 eng(time(0));

inline 
ll randint(ll l, ll r) {
    uniform_int_distribution<ll> dis(l, r);
    return dis(eng);
}

inline 
ll qpow(ll b, ll p, ll mod) {
    ll res = 1;
    for (; p; p >>= 1, b = b * b % mod) if (p & 1) res = res * b % mod;
    return res;
}

inline 
bool check(ll a, ll p) {
    ll s = p - 1, k;
    for (; ~s & 1; s >>= 1);
    for (k = qpow(a, s, p); s != p - 1 && k != 1 && k != p - 1; k = (lll)k * k % p, s <<= 1);
    return k == p - 1 || s & 1;
}

inline 
bool isprime(ll n) {
    if (n == 1) return 0;
    for (int i = 0; i < 7; i++) {
        if (n == prime[i]) return 1;
        if (n % prime[i] == 0 || !check(prime[i], n)) return 0;
    }
    for (int i = 1; i <= 10; i++) if (!check(randint(2, n - 1), n)) return 0;
    return 1;
}

inline 
ll pollard_rho(ll n) {
    if (n == 4) return 2;
    if (isprime(n)) return n;
    for (ll c, t, r, p, q; ;) {
        c = randint(1, n - 1), t = 0, r = 0, p = 1, q;
        auto f = [=](ll x) { return ((lll)x * x + c) % n; };
        do {
            for (int i = 0; i < 128; ++i) {
                t = f(t), r = f(f(r));
                if (t == r || (q = (lll)p * abs(t - r) % n) == 0) break; p = q;
            }
            ll d = __gcd(p, n); if (d > 1) return d;
        } while (t != r);
    }
}

unordered_map<ll, ll> fac;

ll get(ll x) {
    if (fac[x]) return fac[x]; ll k = pollard_rho(x);
    return fac[x] = k == x ? x : fac[x] = max(get(k), get(x / k));
}

unordered_map<ll, int> cnt;

ll t, x[MAXN], y[MAXN]; int n, ans;

int main() {
//  freopen("lovely3.in", "r", stdin);
//  freopen("lovely.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &t), x[i] = y[i] = 1;
        for (ll p; t > 1; t /= p) {
            p = get(t);
            if (x[i] % p == 0) x[i] /= p;
            else if (y[i] % p == 0) y[i] /= p, x[i] *= p;
            else y[i] *= p;
        }
    //  printf("%lld^2*%lld\n", x[i], y[i]);
        cnt[x[i] * x[i] * y[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (cnt[1] && x[i] * y[i] == 1) { ans++, cnt[1] = 0; continue; }
        ll p = x[i] * x[i] * y[i], q = (y[i] <= 1e5 ? y[i] * y[i] * x[i] : -1);
        ans += max(cnt[p], cnt[q]), cnt[p] = cnt[q] = 0;
    }
    printf("%d", ans);
}