noj 2069 赵信的往事 [yy题 无限gcd]

坑爹的无限gcd，，，尼玛想好久，原来要x对y算一次，y再对x算一次，，，

赵信的往事

时间限制(普通/Java) : 1000 MS/ 3000 MS运行内存限制 : 65536 KByte

总提交 : 20测试通过 : 2

描述

赵信——德玛西亚的总管，可谓一人之下，万人之上。但谁能想到，他以前在诺克萨斯的角斗场过的是怎样的生活？

那时，成千上万的奴隶或战俘被抓进角斗场，通过血腥的杀戮供贵族们取乐。所以，为了活下去，除了自身的实力之外，拉帮结派也是必不可少的。显然，这样的事只可能发生在互相信赖的人的中间，而在当时，人们互相信赖的标准却很奇怪——每个人都有一个编号，若两个人可以相互信赖，那么当且仅当这两个编号的素因子集合相同。

那么问题来了：

现在有三个人想组团，请问他们能相互信赖么？

输入

先输入一个正整数T，表示共有T组测试样例，1≤T≤10000。

对于每一个测试样例，输入三个正整数，对于第i个数p_{i，表示第i个人的编号(1≤pi≤10^9)。}

输出

对于每组样例，如果可以可以成功组团，则输出“YES”，否则输出“NO”。

样例输入

2

369

3927

样例输出

NO

YES

提示

对于样例一，6的素因子集合为{2,3},与其他人不同，所以不行；

对于样例二，所有数的素因子集合均为{3},因此可以组团。

题目来源

yuman

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<string> 6 #include<iostream> 7 #include<algorithm> 8 #include<set> 9 #define maxi(a,b) (a)>(b)?(a):(b)10 #define mini(a,b) (a)<(b)?(a):(b)11 #define N 100000512 #define mod 1000013 #define ll long long14 15 using namespace std;16 17 int T;18 int flag;19 int a[5];20 21 int gcd(int x,int y)22 {23if(y==0)24 return x;25return gcd(y,x%y);26 }27 28 void ini()29 {30flag=1;31scanf("%d%d%d",&a[0],&a[1],&a[2]);32//printf("%d %d %d\n",a[0],a[1],a[2]);33sort(a,a+3);34 }35 36 37 void cal(int x,int y)38 {39int g;40if(x==1 && y==1) return;41g=gcd(x,y);42x/=g;43y/=g;44if(x==1 && y==1) return;45else if(g==1 && y%x!=0){46 flag=0;return;47}48else{49 cal(x,g);50}51return;52//}53 }54 55 void solve()56 {57 // printf(" sss\n");58cal(a[0],a[1]);59cal(a[1],a[0]);60if(flag==0) return;61 // printf(" sss2\n");62cal(a[0],a[2]);63cal(a[2],a[0]);64 }65 66 void out()67 {68//printf(" oooo\n");69if(flag==1){70 printf("YES\n");71}72else{73 printf("NO\n");74}75 }76 77 int main()78 {79 // freopen("data.in","r",stdin);80scanf("%d",&T);81while(T--)82 // while(scanf("%I64d",&n)!=EOF)83{84 ini();85 solve();86 out();87}88return 0;89 }