Submission #1517497

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
int x;
vector<int> pr;
int isprime(int x){

int i;
int cou=0;
for(i=2;i<x;i++){
    if(x%i==0)
    {cou++;
    break;
    }

}
if(cou==0)
    return 1;
else
    return 0;
}

int main(){
x=2200;
int n;
int i,j;
cin>>n;
ll a[n+1];
int fl=0;
map<pair<ll,ll>, int> w;
for(i=2;i<x;i++){

    if(isprime(i)){

        pr.pb(i);
    }

}

for(i=1;i<=n;i++)
    cin>>a[i];

    for(i=1;i<=n;i++){
  ll x=a[i],y=1,z=1;
        for(j=0;j<pr.size();j++){
            int cou=0;
            while(x%pr[j]==0){
                    cou++;
            x=x/pr[j];

            }
            cou=cou%3;
            if(cou==1){
                y=y*pr[j];
                z=z*pr[j]*pr[j];
            }
            if(cou==2){

                 z=z*pr[j];
                y=y*pr[j]*pr[j];
            }


        }
        if(x>1){

          ll xx=(ll)sqrt(x);
          if((xx*xx)==x)
          {
              y=y*x;
              z=z*xx;
          }
          else
          {
              y=y*x;
              z=z*(x)*x;
          }


        }

        pair<ll,ll> t=mp(y,z);
        if(y==1&&z==1){
            fl=1;
        }
        else
        w[t]=w[t]+1;
    }
map<pair<ll,ll>, int>::iterator z=w.begin();

int ans=0;

int g=0;
while(z!=w.end()){

    pair<ll,ll> x=(*z).first;



    pair<ll,ll> o;
    o.first=x.second;
    o.second=x.first;
    if(w.find(o)==w.end())
    {ans=ans+w[x];

    }
    else{
        g=g+max(w[o],w[x]);


    }



    z++;

}
ans=ans+g/2;
ans=ans+fl;
cout<<ans<<endl;





return 0;}

Submission Info

Judge Result