zzuli oj 1905: 小火山的跳子游戏_综合

1905: 小火山的跳子游戏

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 445 Solved: 99

SubmitStatusWeb Board

Description

   小火山和火山火山在一块玩跳子游戏。规则如下：
  
   1：跳子的起始位置为0，棋盘大小从1到N
  
   2：每次跳子跳k步。 例如当前位置为i， 那么下一步为i + k
  
   3：跳子过程中，碰到1或N则往回跳。例如当前位置为4， N = 6， K = 5的
  
   时候， 那么下次跳子， 应该是 5， 6， 5 ，4， 3。最后落在3的位置， 再一次
  
   跳子为2 1 2 3 4。最后落在4的位置；
  
   现在小火山想知道经过任意次跳子最后能否将这个棋盘上的每个数字都走过。

Input

   输入第一行是一个整数T（T <= 20000), 表示一共有T组数据。
  
   每一组数据都有两个整数N， K（1 <= K ，N <= 5000)

Output

对于每组数据，如果可以将这个棋盘上的每个数字都走过则输出"Yes", 否则输出"No"

Sample Input

 
42 1 
 

Sample Output

No

Yes

 
  思路：k==1时，1,2,3,4,5，n-1,n,n-1,5,4,3,2,1,可知周期为2*(n-1),把棋盘想像成一个环形，如果每次跳k,若周期能除尽k， 
 

 
  会构成循环，不会扫到所有的点，所以只有互质才满足题意； 
 

 
  代码： 
 

#include<stdio.h>
#include<algorithm>
#include<string.h>
int gcd(int x,int y)
{if(x%y==0)return y;elsereturn gcd(y,x%y);
}
int main()
{int t,n,k;scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);if(k==1){printf("Yes\n");continue;}if(gcd(2*n-2,k)==1)printf("Yes\n");elseprintf("No\n");}return 0;
}