首先对每个数分解只因数，然后把只因数的指数对3取模，把 \(s\) 划分成多个等价类。对于每一个等价类，有唯一对应的另一个等价类不能同时选，取最多的即可。
分解只因数用 polard's rho 算法，时间复杂度 \(O(nw^{0.25})\)
code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MX=1e5+7;
const int tp=10;
ll f[80],cnt;
ll s[MX];
ll myabs(ll a){
return a>0?a:-a;
}
ll gcd(ll x,ll y){
return y==0?x:gcd(y,x%y);
}
ll rd(ll a,ll b){
return 1ll*(1.*rand()/RAND_MAX*(b-a)+0.5)+a;
}
ll mul(ll x,ll y,ll mod){
ll res=x*y-(ll)((long double)x*y/mod+0.5)*mod;
return res<0?res+mod:res;
}
ll qpow(ll x,ll y,ll mod){
ll ret=1;
while(y){
if(y&1)ret=mul(ret,x,mod);
x=mul(x,x,mod);
y>>=1;
}
return ret;
}
ll pr(ll a,ll c){
ll x=rd(0,a-1),y=x,d=1;
for(int i=1,k=1;d==1;i++){
if(((x=mul(x,x,a)+c)%a)==y)return a;
d=gcd(a,myabs(y-x));
if(i==k){
k<<=1;
y=x;
}
}
//cout<<d<<' '<<a<<endl;
//system("pause");
return d;
}
bool check(ll a,ll x){
ll tmp=x-1,j=0;
while(!(tmp&1)){
tmp>>=1;
j++;
}
ll y=qpow(a,tmp,x);
if(y==1||y==x-1)return true;
while(j--){
y=mul(y,y,x);
if(y==x-1)return true;
if(y==1)return false;
}
return false;
}
bool isp(ll x){
if(x%2==0||x<3)return x==2;
for(int i=1;i<=tp;i++){
ll a=rd(2,x-1);
if(!check(a,x))return false;
}
return true;
}
void decom(ll x){
if(x==1)return;
if(isp(x)){
f[++cnt]=x;
return;
}
ll d=x,c=x-1;
while(d==x)
d=pr(x,c--);
while(!(x%d))x/=d;
decom(d),decom(x);
}
map<ll,int > buc;
map<ll,ll > inv;
ll calc(ll x){
cnt=0;
ll ans=x;
decom(x);
sort(f+1,f+1+cnt);
cnt=unique(f+1,f+1+cnt)-(f+1);
ll tx=1,vx=1;
for(int i=1;i<=cnt;i++){
int tmp=0;
while(x%f[i]==0){
x/=f[i];
tmp++;
}
tmp%=3;
if(tmp==1){
tx*=f[i];
vx*=f[i]*f[i];
}
if(tmp==2){
tx*=f[i]*f[i];
vx*=f[i];
}
}
inv[tx]=vx;
inv[vx]=tx;
return tx;
}
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
buc[calc(s[i])]++;
}
ll ans=0;
for(auto it=buc.begin();it!=buc.end();++it){
int x=it->first,num1=it->second;
//cout<<x<<' '<<inv[x]<<' '<<num1<<endl;
if(num1==0)continue;
if(x==1)ans++;
else{
if(buc.find(inv[x])!=buc.end()){
int num2=buc[inv[x]];
if(num1>num2)
ans+=num1;
else
ans+=num2;
buc[x]=buc[inv[x]]=0;
}
else ans+=num1;
}
}
cout<<ans<<endl;
return 0;
}