hdu 2104(藏手帕)
2023-04-12
题目大意：意思是n个人围成一个圈，大家玩丢手帕游戏，手帕藏在某一个人的箱子里，Haha来找，每一次他都会跳过m-1个人。问你Haha是不是一定能找到手帕。因为Haha找的次数是无限的，可以永远找下去，所以，只要他能把所有的人都找一遍就一定能找到。但按照他的这种找法，如果n和m不互质的话，不互质就会出现某些人是永远不会找。所以看一下n和m的最大公约数就行了
解题思路：
判断是否可以遍历所有的盒子，只要盒子数和每次走的步数存在值不等于1的最大公约数时，他就会回到起点，从而做重复的动作。
归根结底，其实就是给出盒子数和步数，判断能否遍历所有盒子。这里有一个规律就是如果和字数和步数互质(最大公约数为1)，那么则能遍历，否则不能遍历。
代码如下：
/*
* 2014_2.cpp
*
* Created on: 2013年8月10日
* 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 n,m;
while(scanf("%d%d",&n,&m)!=EOF){
if(n==-1&&m==-1){
break;
}
//互质,则最大公约数为1
if(mul(n,m) != 1){
printf("POOR Haha\n");
}else{
printf("YES\n");
}
}
} 本文仅代表作者观点，版权归原创者所有，如需转载请在文中注明来源及作者名字。
免责声明：本文系转载编辑文章，仅作分享之用。如分享内容、图片侵犯到您的版权或非授权发布，请及时与我们联系进行审核处理或删除，您可以发送材料至邮箱：service@tojoy.com