赵信的往事
时间限制(普通/Java):1000 MS/3000 MS 运行内存限制 : 65536 KByte总提交 : 209测试通过 : 80
题目描述
赵信——德玛西亚的总管，可谓一人之下，万人之上。但谁能想到，他以前在诺克萨斯的角斗场过的是怎样的生活？
那时，成千上万的奴隶或战俘被抓进角斗场，通过血腥的杀戮供贵族们取乐。所以，为了活下去，除了自身的实力之外，拉帮结派也是必不可少的。显然，这样的事只可能发生在互相信赖的人的中间，而在当时，人们互相信赖的标准却很奇怪——每个人都有一个编号，若两个人可以相互信赖，那么当且仅当这两个编号的素因子集合相同。
那么问题来了：
现在有三个人想组团，请问他们能相互信赖么？
输入
先输入一个正整数T，表示共有T组测试样例，1≤T≤10000。
对于每一个测试样例，输入三个正整数，对于第i个数pi，表示第i个人的编号(1≤pi≤109)。
输出
对于每组样例，如果可以可以成功组团，则输出“YES”，否则输出“NO”。
样例输入
2
369
3927
样例输出
NO
YES
提示
对于样例一，6的素因子集合为{2,3},与其他人不同，所以不行；
对于样例二，所有数的素因子集合均为{3},因此可以组团。
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int MAXN=100000+100;typedef long long ll;int vis[MAXN],prime[MAXN];int x,y,z,cnt;int main(){cnt=0;memset(vis,0,sizeof(vis));for(ll i=2;i<MAXN;i++){if(!vis[i])prime[++cnt]=i;for(ll j=i*i;j<MAXN;j+=i)vis[j]=1;}int T;scanf("%d",&T);while(T--){scanf("%d%d%d",&x,&y,&z);int i=1,flag=1;while(x!=1){if(x%prime[i] == 0){if(y%prime[i] || z%prime[i]){flag=0;break;}while(x%prime[i] == 0){x/=prime[i];}while(y%prime[i] == 0)y/=prime[i];while(z%prime[i] == 0)z/=prime[i];}i++;if(i>cnt)break;}if(x == 1 && (y!=1 || z!=1))flag=0;if(x!=1 && (y%x!=0 || z%x!=0))flag=0;if(flag)printf("YES\n");elseprintf("NO\n");}return 0;}
这是恺学长的题解，起初提交的时候总超时，学长人好把代码借我了。。。
主要是素数的预处理~~~
