nyoj 189 兔子的烦恼(一）(辗转相除法求最大公约数)

nyoj 189 兔子的烦恼(一）(辗转相除法求最大公约数)

题目189​​题目信息​​​​运行结果​​​​本题排行​​​​讨论区​​

兔子的烦恼(一）

1000 ms  |  内存限制： 65535

2

在一座山上有n个山洞（每个洞从0~n-1分别编号），这山上有一只兔子躲在山洞里，有一只狼，从编号为0的山洞开始入洞，每隔m-1个洞，再次入洞抓兔子，现在问，兔子能否避免这场灾难？

例如：m=2 and n=6, 狼将要进入的山洞号为：0,2,4,0;

有多组测试数据，不超过1000组;

每组有两个整数m,n(0

注意：程序以文件结束符“EOF”结束输入。

输出 兔子能避免这场灾难输出YES，否则输出NO; 样例输入

1 22 2

样例输出

NOYES

​

这道题说到底就是求m和n的最大公约数。在杭电上也做过这道题，不是用的这样的方法。结果同样的方法在这里wa了，说明在杭电做的方法错了。也说明杭电的这道题的数据很水。

#includeint gcd(int m,int n){ int temp,r; if(m>n) temp=m,m=n,n=temp; while(m) r=n%m,n=m,m=r; return n;}int main(){ int m,n; while(scanf("%d %d",&m,&n)!=EOF) { if(m==1||n==1) { printf("NO\n"); continue; } if(gcd(m,n)==1) printf("NO\n"); else printf("YES\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。