hdu 1222(狼找兔子——辗转相除法)
2023-04-12
题目大意:一座山围绕着n个山洞(兔子藏在其中一个山洞中),现在狼每m个山洞就进去找一下,输出是否存在安全的山洞(即狼没有进去找的山洞)。
解题思路:这一道题和2104那道找手帕的题目其实是一样的。这个问题抽象一下，就是"有n个山洞，每m个访问一下，看是否能遍历所有的山洞"
1)两个数只要互质，就能遍历。
2)用辗转相除法(返回的是两个数的最大公约数)来判断是否互质。如果返回1，那么这两个数互质，所以可以遍历。否则不可以遍历。
代码如下：
/*
* 1222_1.cpp
*
* Created on: 2013年8月11日
* Author: Administrator
*/
#include
/**
* 辗转相除法,用来求最大公约数
*/
int mul(int a , int b){
int temp;
while(b != 0){
temp = b;
b = a%b;
a= temp;
}
return a;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int a,b;
scanf("%d%d",&b,&a);
if(mul(a,b) != 1){
printf("YES\n");
}else{
printf("NO\n");
}
}
} 本文仅代表作者观点，版权归原创者所有，如需转载请在文中注明来源及作者名字。
免责声明：本文系转载编辑文章，仅作分享之用。如分享内容、图片侵犯到您的版权或非授权发布，请及时与我们联系进行审核处理或删除，您可以发送材料至邮箱：service@tojoy.com