Submission #9160976

---

Source Code Expand

 // ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>  
#include <cmath>
#include <map>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,L=2155+10;

int n; ll a[N],x[N],y[N];
map<ll,int> o,vis;

int v[N],p[N],cnt=0;
inline void sieve(int n) {
    for (re int i=2;i<=n;++i)  {
        if (!v[i]) p[++cnt]=i;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
}

int main() { sieve(2155);
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) {
        x[i]=y[i]=1;
        for (re int j=1;j<=cnt;++j) {
            if (a[i]%p[j]==0) { int c=0;
                while (a[i]%p[j]==0) ++c,a[i]/=p[j];
                if (c%3==1) x[i]*=p[j],y[i]*=p[j]*p[j];
                if (c%3==2) x[i]*=p[j]*p[j],y[i]*=p[j];
                if (a[i]==1) break;
            }
        }
        if (a[i]>1) {
            ll r=sqrt(a[i]);
            if (r*r==a[i]) x[i]*=r*r,y[i]*=r;
            else x[i]*=a[i],y[i]*=a[i]*a[i];
        }
    }
    int ans=0,flag=0;
    for (re int i=1;i<=n;++i) ++o[x[i]];
    for (re int i=1;i<=n;++i) {
        if (vis[x[i]]) continue;
        if (x[i]==1) flag=1;
        else ans+=max(o[x[i]],o[y[i]]),vis[x[i]]=vis[y[i]]=1;
    }
    printf("%d\n",ans+flag);
    return 0;
}

Submission Info

Judge Result