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 Z喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcmRlci4gVGhlIGZpcnN0IGhvbGUgaGUgZ2V0IGludG8gaXMgdGhlIG9uZSBzaWduZWQgd2l0aCAwLiBUaGVuIGhlIHdpbGwgZ2V0IGludG8gdGhlIGhvbGUgZXZlcnkgbSBob2xlcy4gRm9yIGV4YW1wbGUsIG09MiBhbmQgbj02LCB0aGUgd29sZiB3aWxsIGdldCBpbnRvIHRoZSBob2xlcyB3aGljaCBhcmUKIHNpZ25lZCAwLDIsNCwwLiBJZiB0aGUgcmFiYml0IGhpZGVzIGluIHRoZSBob2xlIHdoaWNoIHNpZ25lZCAxLDMgb3IgNSwgc2hlIHdpbGwgc3Vydml2ZS4gU28gd2UgY2FsbCB0aGVzZSBob2xlcyB0aGUgc2FmZSBob2xlcy48YnI+CgoKIAo8YnI+CgpJbnB1dAoKVGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgcG9zaXRpdmUgaW50ZWdlciBQIHdoaWNoIGluZGljYXRlcyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIFRoZW4gb24gdGhlIGZvbGxvd2luZyBQIGxpbmVzLGVhY2ggbGluZSBjb25zaXN0cyAyIHBvc2l0aXZlIGludGVnZXIgbSBhbmQgbigwPG0sbjwyMTQ3NDgzNjQ4KS48YnI+CgoKIAo8YnI+CgpPdXRwdXQKCkZvciBlYWNoIGlucHV0IG0gbiwgaWYgc2FmZSBob2xlcyBleGlzdCwgeW91IHNob3VsZCBvdXRwdXQg"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

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;
}