题目：Description
在一个遥远的地方，有一座不知名的高山，周围有 n 个兔子的窝，分别标记为 0 至 n-1 。小白兔隐藏在其中，大灰狼从 0 号窝开始按着逆时针的方向寻找，每隔 m 个洞查找一次。 例如： n = 6, m = 2, 则大灰狼寻找窝的序号依次为 0，2，4，0,...。如果小白兔藏在1，3，或5号窝中，那么小白兔则会很安全。
Input
输入以一个正整数P开始，表示有P组测试数据，接着有P行，每行有两个正整数 m 和 n (0 < m,n < 2147483648)。
Output
对于输入的每组 m 和 n, 如果有安全的窝存在，输出 "YES" ,否则输出 "NO"。
我的代码：

#include<stdio.h>
int f(int m,int n)
{
    int y;
    if ((m%n==0 || n%m==0) && (m!=1 && n!=1)) y=1;
    else y=0;
    return y;
}
void main()
{
    int p,m,n;
    scanf("%d",&p);
    while(p>0)
    {
        scanf("%d%d",&m,&n);
        if(f(m,n)==1) printf("YES\n");
        else printf("NO\n");
        p--;
    }
}

我觉这道题应该是考整数互质吧。求高手指出哪里还有漏洞。。

互质是这样测试的吗。你这个是测试约数的

感谢2楼!

昨天想了一下这题，其实这题的证明还是蛮有趣的，在这里求证明，第一个给出完整证明的我开个百分贴送分

呵呵，小曹把这个问题变的有意思了。要完整的证明？等一下，我组织一下语言。

根据楼主的描述，这个问题等同于问 (i * m) 除以 n有多少个不同的余数（i为正整数）。

先设m与n的最大公约数为a，m与n的最小公倍数为b。

那么 b = n * m / a；

(i * m) mod n == (i * m + b) mod n
              == ((i + n / a) * m) mon n

由上式可以看出，(i * m) mod n 的结果是一个周期函数，它的一个周期是 n / a。

这意味着 (i * m) mod n 最多有 n / a 个不同的解。

注意我的措词，是最多。以上的证明只能说明它不可能超过 n / a 个。

还存在的可能是余数的个数小于 n / a 个。

下面来讨论这一点，（i * m) mod n 的不同解的个数是否可以小于 n / a。

限于我的数论水平，关于这一点，我没法直接证明，我将使用反证法来证明。

假设(i * m) mod n 的不同解的个数可以小于 n / a。

这意味着在[1, n / a]的范围内至少存在两个数 i、j（i不等于j)，使得

（i * m) mod n == (j * m) mod n

不妨假设 i < j， 那么由上式可得

((j - i) * m) mod n == 0

即

(j - i) * m == k * b

(j - i) = k * n / a

由于 i != j， 所以 j - i != 0， 即 k 不等于0

所以 j = i + k * n / a

由此 j > n / a

这与之前的假设 i、j 在[1，n / a]的范围内矛盾。

所以在[1, n / a]的范围内不存在两个不相等的数i、j，使得 (i * m) mod n == (j * m) mod n

由此证明 (i * m) mod n 的不同解的个数为 n / a。

对于楼主的问题，只有狼查遍了所有的洞才能抓到兔子。换句话说，只要它漏掉一个洞，那么兔子就可以躲在这个洞里活下来。

狼要想查遍所有的洞，就要求

n / a == n

由之前a的定义，这意味着 m 和 n 的最大公约数为1, 也就是说 m 和 n 互素。

证毕。

由上面的证明也可以知道兔子的安全洞的数量为 n - n / gcd(n, m) 个。只要这个值大于0，兔子就是安全的。

杨大哥这个利用周期函数卡上下界确实蛮犀利的，其实我觉得和我那个证明中有一个地方也蛮像的，我贴一下我的证明:

问题等同于i*m mod n有多少种可能

首先如果gcd(n,m)>1,又可知i*m mod n一定是gcd(n,m)的倍数，所以非其倍数的洞就无法达到，自然是安全的

然后证明当gcd(n,m)=1时可以到达所有的洞

考虑下面n个数
0*m mod n
1*m mod n
2*m mod n
.
.
(n-1)*m mod n

如果其中有两个数相等，我们设第i,j个数相等，则aj-ai=0

又因为aj-ai可以表示成(j-i)*m mod n的形式，且(j-i)的取值范围为[1,n-1],由于gcd(n,m)=1,所以(j-i)*m mod n肯定不等于0，所以第i,j个数不可能相等

既然这n个数不相等，那么肯定包括了0--n-1这n个洞，所以当n,m互质时就肯定会被抓住

突然想到这个只是想交流一下这题的证明，因为我记得刚学编程的时候遇到过这题，当时不会证明，就直接感性得认识了一下，昨天又遇到了这个题目就忍不住证了一下。

至于分数，杨大哥应该不在意这点分吧，我也不是很在意，只是觉得没必要再专门开一贴了

呵呵，参与你的讨论并不是为了你的分，只是对你提出的问题感兴趣

以后有这样有趣的问题多提出来大家讨论。我很享受这个讨论的过程。

这个帖子在你发贴前我早就看过了，呵呵，如果为了分我会比你先回答的

C/C++交流进群 76406740
一起交流，学习