关键是那些两个数相乘拼成了立方数的
一个数分解质因数后，指数%3是不影响的
我们可以这样想——我们通过一个数，反推出能够和他凑成立方数的数
但有可能这个数在原序列里不存在 不过没关系 我们开两个桶 每次比较下大小 只往一边放 这样就不会多统计了
#include<bits/stdc++.h> #define N 100005 #define int long long using namespace std; template<class T> inline void read(T &x) { x=0; int f=1; static char ch=getchar(); while((!isdigit(ch))&&ch!='-') ch=getchar(); if(ch=='-') f=-1; while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); x*=f; } int prime[N],cnt,np[N],minp[N]; void Pick() { np[0]=np[1]=1; for(int i=2;i<=1e5;i++) { if(!np[i]){ minp[i]=i; prime[++cnt]=i; } for(int j=1;j<=cnt&&i*prime[j]<=1e5;j++) { np[i*prime[j]]=1; minp[i*prime[j]]=prime[j]; if(!(i%prime[j])) break; } } } typedef pair<int,int> Pair; int n,a[N],b[N]; inline Pair split(int x) { int a=1,b=1; while(x!=1) { int p=minp[x],up=0; while(!(x%p)) x/=p,++up; up%=3; if(up) (up==1)?(a*=p,b*=p,b*=p):(a*=p,a*=p,b*=p); } return Pair(a,b); //注意 a是肯定存在的 } int le[N],ri[N]; main() { Pick(); read(n); int temp=0,ans=0; for(register int i=1;i<=n;i++) { read(a[i]),read(b[i]); Pair now=split(a[i]); if(now.first==1) temp=max(temp,b[i]); else { if(now.first<now.second) le[now.first]+=b[i]; else ri[now.second]+=b[i]; } } for(int i=2;i<=1e5;i++) ans+=max(le[i],ri[i]); cout<<ans+temp; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9883886.html
相关资源：各显卡算力对照表！