XTU-OJ 1343-青蛙-Toy模板网

这篇具有很好参考价值的文章主要介绍了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代码：文章来源地址https://www.toymoban.com/news/detail-724897.html

#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-青蛙的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！