Submission #1776845

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair

ll read()
{
    ll v = 0, f = 1;
    char c = getchar();
    while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
    while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
    return v * f;
}

map<ll, ll> mp;
ll pr[101000], vis[101000], a[101000], b[101000], n;

const ll INF = 1e12;

const ll p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
inline ll mul(ll a, ll b, ll p)
{
    ll t = ll((double) a * b / (double) p + 0.5);
    t = a * b - p * t;
    return t < 0 ? t + p : t;
}
inline ll pw(ll a, ll b)
{
    ll re = 1;
    while (b)
    {
        if (b & 1)
            re *= a;
        a *= a;
        b >>= 1;
    }
    return re;
}
inline ll pw(ll a, ll b, ll p)
{
    ll re = 1;
    while (b)
    {
        if (b & 1)
            re = mul(re, a, p);
        a = mul(a, a, p);
        b >>= 1;
    }
    return re;
}
inline bool millerRabbin(ll n)
{
    if (n < 29)
    {
        for (int i = 0; i < 9; i++)
            if (p[i] == n)
                return 1;
        return 0;
    }
    ll d = n - 1;
    int s = 0;
    while (d % 2 == 0)
        d /= 2, s++;
    for (int i = 0; i < 9; i++)
    {
        ll j = p[i];
        ll t = pw(j, d, n);
        for (int is = 0; is < s; is++)
        {
            ll tmp = mul(t, t, n);
            if (tmp == 1)
                if (t != 1 && t != n - 1)
                    return 0;
            t = tmp;
        }
        if (t != 1) return 0;
    }
    return 1;
}
ll num[10000];
ll rho(ll n)
{
	ll c = rand() % (n - 1) + 1;
	ll p1 = 1, p2 = 1, k = 1, t = 1;
	for (ll i = 1; t == 1; i++)
	{
		p1 = (mul(p1, p1, n) + c) % n;
		if (p1 == p2) return 1;
		t = __gcd(abs(p1 - p2), n);
		if (i == k) k += k, p2 = p1;
	}
	return t;
}
void cal(ll n)
{
    if (millerRabbin(n))
    {
        num[++num[0]] = n;
        return ;
    }
    ll t = 1;
    while (t == 1)
        t = rho(n);
    cal(t);
    cal(n / t);
}

int main()
{
    n = read();
    for (int i = 2; i <= 100000; i++)
    {
        if (!vis[i])
            pr[++pr[0]] = i;
        for (int j = 1; j <= pr[0] && i * pr[j] <= 100000; j++)
        {
            vis[i * pr[j]] = 1;
            if (i % pr[j] == 0) break;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        ll u = read();
        num[0] = 0;
        cal(u);
        map<ll, int> t;
        for (int j = 1; j <= num[0]; j++)
            t[num[j]]++;
        ll p1 = 1, p2 = 1;
        for (map<ll, int> :: iterator j = t.begin(); j != t.end(); j++)
        {
            int t1 = (*j).second % 3;
            int t2 = (3 - t1) % 3;
            p1 *= pw((*j).first, t1);
            if (pw((*j).first, t2) <= INF / p2)
                p2 *= pw((*j).first, t2);
            else
                p2 = INF;
        }
        a[i] = p1;
        b[i] = p2;
        if (p1 > 1)
            mp[p1]++;
    }
    ll ans = 0;
    set<ll> S;
    for (int i = 1; i <= n; i++)
        if (a[i] > 1 && !S.count(a[i]))
        {
            ans += max(mp[a[i]], mp[b[i]]);
            S.insert(a[i]);
        }
    ans /= 2;
    ll flg = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] == 1) flg = 1;
    printf("%lld\n", ans + flg);
}

Submission Info

Judge Result