程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1222 Wolf and Rabbit (GCD)

hdu 1222 Wolf and Rabbit (GCD)

編輯:C++入門知識

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





  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved