Submission #1189138

---

Source Code Expand

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>

using namespace std;

typedef long long ll;

const int p = 900000009;

void Sito(vector<int>& P)
{
    vector<bool> p(2500, true);
    p[0] = p[1] = false;
    for (int i = 2; i < 2500; ++i)
        if (p[i])
            for (int j = 2 * i; j < 2500; j += i)
                p[j] = false;
    for (int i = 0; i < 2500; ++i)
        if (p[i])
            P.push_back(i);
}

int Hasz(vector<ll>& a)
{
    int h = 0;
    for (int i = 0; i < a.size(); ++i)
        h = h * p + a[i];
    return h;
}

bool Kw(ll x)
{
    ll pie = sqrt(x);
    if (pie * pie == x)
        return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    vector<int> P;
    Sito(P);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    map<int, int> M;
    multiset< pair<int, int> > S;
    bool jed = false;
    for (int i = 0; i < n; ++i)
    {
        vector<ll> po, wyk;
        for (int j = 0; j < P.size(); ++j)
        {
            int il = 0;
            while (a[i] % P[j] == 0)
            {
                a[i] /= P[j];
                ++il;
            }
            if (il % 3 != 0)
            {
                po.push_back(P[j]);
                wyk.push_back(il % 3);
            }
        }
        if (a[i] != 1)
        {
            if (Kw(a[i]))
            {
                po.push_back(sqrt(a[i]));
                wyk.push_back(2);
            }
            else
            {
                po.push_back(a[i]);
                wyk.push_back(1);
            }
        }
        if (po.size() == 0)
        {
            jed = true;
            continue;
        }
        vector<ll> odp;
        for (int j = 0; j < wyk.size(); ++j)
        {
            if (wyk[j] == 1)
                odp.push_back(2);
            if (wyk[j] == 2)
                odp.push_back(1);
        }
        int hpo = Hasz(po);
        int hwyk = Hasz(wyk);
        int hodp = Hasz(odp);
        M[hwyk] = hodp;
        M[hodp] = hwyk;
        S.insert(make_pair(hpo, hwyk));
    }
    int odp = 0;
    while (S.size() != 0)
    {
        pair<ll, ll> a = *S.begin();
        int il1 = 0;
        while (S.size() != 0 && (*S.begin()).first == a.first && (*S.begin()).second == a.second)
        {
            S.erase(S.begin());
            ++il1;
        }
        pair<ll, ll> b = make_pair(a.first, M[a.second]);
        int il2 = 0;
        while (S.size() != 0 && S.find(b) != S.end())
        {
            S.erase(b);
            ++il2;
        }
        odp += max(il1, il2);
    }
    if (jed)
        ++odp;
    cout << odp;
    return 0;
}

Submission Info

Judge Result