本文主要是介绍XTU-OJ 1343-青蛙，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
有n个位置按顺时钟排列成一个圆，分别编号从1∼n。一只青蛙最开始在1号位置上，它每次可以跳往与之相隔k个位置的位置上。比如，n=5,k=2时， 青蛙从位置1可以按逆时钟方向跳到位置3，也可以按顺时钟方向跳到位置4。请问这只青蛙能跳到所有的位置上吗？
输入
第一行输入一个整数 T(1≤T≤1000),表示样例的个数。 以后每行一个样例，为两个整数n(1≤n≤109),k(0≤k≤n−2)。
输出
每行输出一个样例的结果。如果青蛙可以到达所有位置，输出"Yes"，否则输出"No".
样例输入
2 5 2 4 1样例输出
Yes No样例解释
第一个样例，青蛙一直按顺时钟跳，依次的位置为 1,4,2,5,3； 第二个样例，青蛙只能跳到1,3两个位置。
解题思路： 题目这个 k 给的就很迷惑，他说的是 相隔k个，不想太麻烦，就直接把他转换成 青蛙每次可以跳 k+1 个位置。
其实我不想解释，因为我发现，我说出来反而会把简单的问题说得复杂，暂时没想到如何解释出来。先凑合看吧，等我之后再更新。如果看不懂直接看最后一句注红的。
咱们想想，这是一个圆圈一个环，要把所有的位置都跳到，只跳一圈是不可能做到的（除非k=0）。 第一圈跳的位置都是 n*k+1 (n=0,1,2,3....)，如果要完成 题目目标，那第二轮乃至后面的轮次，要和前面跳的不同，即起始位置要不同。（第一轮是从位置1，那之后肯定要从位置2、位置3····或者位置k开始，不然就重复起跳了，就不可能完成任务）， 那怎么才能避免不在重复的位置反复跳呢？
找 n 和 k+1 有没有公因数，如果有公因数，说明n能整除k+1，那么每一圈，青蛙都会跳满一个完整的⚪，然后回到起始点1。（可以画图模拟一下）。而如果不能整除，青蛙就不会跳出一个完整的⚪，所以到下一圈就可以跳到不是1的位置，以此往复，就可以跳满整个圆。
AC代码：
#include <stdio.h>int gcd(int x,int y){return y>0 ? gcd (y,x%y) : x;
}int main()
{int T,n,k;scanf("%d",&T);while ( T --){scanf("%d %d",&n,&k);if (gcd(n,k+1) == 1) puts("Yes");else puts("No");}return 0;
}这篇关于XTU-OJ 1343-青蛙的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
