Submission #1515710

---

Source Code Expand

#include <bits/stdc++.h>
#include <math.h>
#define uint unsigned long long
#define ll long long
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define eps 1e-9

using namespace std;
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
const int N = 100010;
const int mod = 1e9 + 7;
ll a[N], b[N], aa[N], bb[N];
map<ll, int> Mp;
vector<int> p;
bool vis[N];
int main()
{
    int n,ans = 0;
    rep(i, 2, N - 1)
        if (!vis[i])
        {
            p.push_back(i);
            for (int j = i + i; j < N; j += i) vis[j] = 1;
        }
    cin >> n;
    rep(i, 0, n - 1)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    rep(i, 0, n - 1)
    {
        aa[i] = 1, bb[i] = 1;
        int nn = p.size();
        rep(j, 0, nn - 1)
        {
            int cnt = 0;
            while (a[i] % p[j] == 0)
            {
                a[i] /= p[j];
                cnt ++;
            }
            if (cnt % 3 == 1) aa[i] *= p[j], bb[i] *= p[j] * p[j];
           	else if (cnt % 3 == 2) bb[i] *= p[j], aa[i] *= p[j] * p[j];
        }
        aa[i] *= a[i];
        ll t = floor(sqrt(a[i] * 1.0));
        if (t * t == a[i]) bb[i] *= t;
        else
        {
            if (bb[i] * a[i] > 0 && bb[i] * a[i] * a[i] > 0) bb[i] *= a[i] * a[i];
            else bb[i] = 0;
        }
        Mp[aa[i]] ++;
    }
    int flag = 0;
    rep(i, 0, n - 1)
    {
        if (aa[i] == 1)
        {
            if (flag == 0) ans ++, flag = 1;
        }
        else ans += max(Mp[aa[i]], Mp[bb[i]]), Mp[aa[i]] = Mp[bb[i]] = 0;
    }
    cout << ans;
    return 0;
}

Submission Info

Judge Result