【筛法求素数】Codeforces Round #426 (Div. 1) A. The Meaningless Game
先筛出来1000以内的素数。
枚举x^(1/3) 和 y^(1/3)以内的素因子，这样除完以后对于x和y剩下的因子，小的那个的平方必须等于大的。
然后判断每个素因数的次数之和是否为3的倍数，并且小的那个次数不小于大的次数的两倍。
当然这题是有O（1）的做法哒。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
bool vis[100010];
int pr[100010],e;
void Shai()
{
vis[1]=true;
for(long long i=2;i<=1000ll;i++){
if(!vis[i]){
pr[++e]=i;
for(long long j=i*i;j<=1000ll;j+=i){
vis[j]=true;
}
}
}
}
int n,cnta[100010];
int main(){
Shai();
int x,y;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&x,&y);
int X=x;
for(int j=1;j<=e;++j){
if(X%pr[j]==0){
while(X%pr[j]==0){
X/=pr[j];
++cnta[j];
}
}
}
bool lose=0;
for(int j=1;j<=e;++j){
int cntb=0;
if(y%pr[j]==0){
while(y%pr[j]==0){
y/=pr[j];
++cntb;
}
}
if((cnta[j]+cntb)%3!=0){
lose=1;
break;
}
else if(min(cnta[j],cntb)*2<max(cnta[j],cntb)){
lose=1;
break;
}
}
if(!(X==1 && y==1) && !((ll)min(X,y)*(ll)min(X,y)==(ll)max(X,y))){
lose=1;
}
for(int j=1;j<=e;++j){
cnta[j]=0;
}
if(!lose)
puts("Yes");
else
puts("No");
}
return 0;
}