hdu 1222 Wolf and Rabbit （GCD）

Wolf and Rabbit

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 5502    Accepted Submission(s): 2765

Problem Description There is a hill with n holes around. The holes are signed from 0 to n-1.

A rabbit must hide in one of the holes. A wolf searches the rabbit in anticlockwise order. The first hole he get into is the one signed with 0. Then he will get into the hole every m holes. For example, m=2 and n=6, the wolf will get into the holes which are signed 0,2,4,0. If the rabbit hides in the hole which signed 1,3 or 5, she will survive. So we call these holes the safe holes.

Input The input starts with a positive integer P which indicates the number of test cases. Then on the following P lines,each line consists 2 positive integer m and n(0<m,n<2147483648).

Output For each input m n, if safe holes exist, you should output "YES", else output "NO" in a single line.

Sample Input

2
1 2
2 2
        

Sample Output

NO
YES
  
  

        

題意：一狼一兔，狼圍繞一個均勻分布着n個兔子洞的山轉圈，狼每經過m個洞口，就會進入洞中，那麼這個洞就是不安全的。問n個洞中，是否存在安全的洞讓兔子藏身才能不是可愛的兔子慘遭毒手呢。

解析：開始想的時候，最先想到的就是，如果n % m == 0，那麼就存在。但是當m == n == 1時，就不成立了，并且還存在n < m的情況，同樣也可能不存在安全的洞穴。是以，就不能這麼簡單的想了。後來發現隻要兩者互素，即gcd（n， m）== 1，就存在安全洞穴，否則不存在。

PS：本題由于資料很大，不能用遞歸版本的gcd，必逾時！！！是以，還是手動寫非遞歸版本吧。

AC代碼：

#include<stdio.h>

int gcd(int n, int m){          //非遞歸的gcd
  while(m!=0)
  {
      int t=n%m;
      n=m;
      m=t;
  }
  return n;  
}


int main()
{
    int m,n,i,k;
    scanf("%d",&k);
    for(i=1;i<=k;i++){
        scanf("%d%d",&n,&m);
        printf("%s\n", gcd(n, m) == 1 ? "NO" : "YES");
    }
    return 0;
}