暑假集訓(4)第五彈——— 數論（hdu1222），數論hdu1222
題意概括：那天以後，你好說歹說，都快煉成三寸不爛之捨之際，小A
總算不在擺著死人臉，鼓著死魚眼。有了點恢復的征兆。可孟子這家伙
說的話還是有點道理，那什麼天將降....額，總之，由於賢者法陣未完
成，而小A又遲遲不現身，FFF團團長連下七道聖火令追殺你們，最先趕
到地，機械化部隊，它們除了智能不高外，可以說是無懈可擊。
這正是你要利用的一點，利用他們的行動軌跡，躲藏起來。
問題分析：首先用輾轉相除法求得gcd（n,m),若n>m 則gcd（n,m)為一可逃
反之，非一可逃。
![]()
1 #include "cstdio"
2
3 int main()
4 {
5 int m,n,t,x;
6 scanf ("%d",&t);
7 while (t-- && scanf("%d%d",&n,&m))
8 {
9 while(n % m != 0)
10 {
11 x = m;
12 m = n%m;
13 n = x;
14 }
15 if (n >= m)
16 printf ("%s\n",m==1?"NO":"YES");
17 else
18 printf ("%s\n",m==1?"YES":"NO");
19 }
20 return 0;
21 }
View Code
