数学--数论--HDU1222 狼和兔子（最大公约数）

问题描述

有一座周围有n个洞的小山。孔从0到n-1有符号。

兔子必须藏在其中一个洞中。狼以逆时针方向搜索兔子。他第一个进入的洞是一个用0签名的洞。然后，他将每m个洞进入一个洞。例如，m = 2和n = 6，狼将进入带有符号0,2,4,0的孔。如果兔子躲在标有1,3或5的孔中，它将存活。因此，我们将这些孔称为安全孔。

输入项

输入以表示测试用例数量的正整数P开头。然后在随后的P线上，每行包括2个正整数m和n（0 <m，n <2147483648）。

输出量

对于每个输入mn，如果存在安全孔，则应输出“ YES”，否则输出“ NO”。

样本输入

2

1 2

2 2

思路：m和n如果有公约数，则安全洞存在，无公约数或公约数为1，则无

#include <stdio.h>

int gcd(int a,int b)

{

    if(b==0)return a;

    else

    {

        int r;

        while(b!=0)

        {

            r=a%b;

            a=b;

            b=r;

        }

        return a;

    }

}

int main()

{

    int p,n,m;

    scanf("%d",&p);

    while(p--)

    {

        scanf("%d%d",&m,&n);

        if(gcd(m,n)==1)printf("NO\n");

        else printf("YES\n");

    }

    return 0;

}

巴特西

数学--数论--HDU1222 狼和兔子（最大公约数）

最新文章

热门文章