传送门

如果每个数都不大的话,我们可以把每个数的每个质因子的次数模3,这样两个数乘起来为立方数当且仅当这两个数出现过的质因子一样,且每个质因子一个次数是1,一个次数是2。同样,我们可以把每个数对应的另一个数也预处理出来,然后把同类合并一下就可以统计答案了。

然而本题中数都比较大,不好直接分解。我们考虑按$X^{1/3}$分块($X$是$s_i$的范围),把每个数在$[2,X^{1/3}]$内的质因子拿出来,这一步的复杂度是每个数$O(X^{1/3})$的。然后剩下的数可能是一个大质数,一个大质数乘另一个大质数,或者一个大质数的平方。我们可以直接暴力开方看下是不是大质数的平方,然后分类讨论一下就行了。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#define MAXN 100010
#define LL long long
using namespace std;

int n;
map<LL,int> S;
LL a[MAXN],b[MAXN];
int prime[MAXN],nump;
bool flag[MAXN];

pair<LL,LL> trans(LL x){
    LL tx=x;
    LL y1=1,y2=1;
    for(int _i=1;_i<=nump;_i++){
        LL i=prime[_i];
        if(tx%i==0){
            int cnt=0;
            while(tx%i==0) tx/=i,cnt++;
            cnt%=3;
            for(int j=0;j<cnt;j++) y1*=i;
            cnt=(3-cnt)%3;
            for(int j=0;j<cnt;j++) y2*=i;
        }
    }
    if(tx>1){
        LL temp=max((LL)(sqrt(tx)-2),1LL);
        for(LL i=0;i<4;i++)
            if((temp+i)*(temp+i)==tx){
                y1*=tx;
                y2*=temp+i;
                return make_pair(y1,y2);
            }
        y1*=tx;
        y2*=tx*tx;
    }
    return make_pair(y1,y2);
}

int main(){
#ifdef DEBUG
    freopen("D.in","r",stdin);
#endif
    for(int i=2;i<=2154;i++){
        if(!flag[i]) prime[++nump]=i;
        for(int j=1;j<=nump && i*prime[j]<=2154;j++){
            flag[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
        pair<LL,LL> temp=trans(a[i]);
        a[i]=temp.first;
        b[i]=temp.second;
        S[a[i]]++;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        if(S[a[i]]){
            if(a[i]==1){
                S[a[i]]=0;
                ans++;
                continue;
            }
            int t1=S[a[i]],t2=S[b[i]];
            S[b[i]]=S[a[i]]=0;
            ans+=max(t1,t2);
        }
    printf("%d\n",ans);
}