【暑期第二次训练赛】小火山的跳子游戏

àì夳堔傛蜴生んèń 2022-07-19 05:57 136阅读 0赞

## 1905: 小火山的跳子游戏 ##

Time Limit: 1 Sec Memory Limit: 128 MB  
Submit: 437 Solved: 95  
  
[Submit][] [Status][] [Web 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 ##

26 42 1

## Sample Output ##

NoYes

## HINT ##

## Source ##

[zzuli][]

周期为2\*n-2.

如果k=1的话是1,2,3,4...n-1,n,n-1...3,2,1。可以看出这个周期是2\*n-2，所以只要gcd(2\*n-2, k)==1就是可以全部标记完的。因为走到一个走 过的并且方向一样并且没有标记全部的话就不可能能标记完了，所以要走2\*n-2次没有重复位置和方向的，也就是gcd(2\*n-2,k)==1.

#include<stdio.h>
    int gcd(int a,int b) {
    	if(a%b==0)
    		return b;
    	else
    		return gcd(b,a%b);
    }
    int main() {
    	int T;
    	scanf("%d",&T);
    	while(T--) {
    		int n,k,temp;
    		scanf("%d%d",&n,&k);
    		temp=gcd(2*n-2,k);
    		if(temp==1)
    			printf("Yes\n");
    		else
    			printf("No\n");
    	}
    	return 0;
    }

[题目地址：http://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1905][http_acm.zzuli.edu.cn_zzuliacm_problem.php_id_1905]

[Submit]: http://acm.zzuli.edu.cn/zzuliacm/submitpage.php?id=1905
[Status]: http://acm.zzuli.edu.cn/zzuliacm/problemstatus.php?id=1905
[Web Board]: http://acm.zzuli.edu.cn/zzuliacm/bbs.php?pid=1905
[zzuli]: http://acm.zzuli.edu.cn/zzuliacm/problemset.php?search=zzuli
[http_acm.zzuli.edu.cn_zzuliacm_problem.php_id_1905]: http://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1905