Wolf and Rabbit

2
1 2
2 2

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