设为首页 加入收藏

TOP

hdu 2104
2014-11-23 20:10:37 来源: 作者: 【 】 浏览:10
Tags:hdu 2104

题目大意:意思是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");  
        }  
    }  
}  

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇nyist 284 && poj 2312 坦克大战(.. 下一篇hdu4336

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·微服务 Spring Boot (2025-12-26 18:20:10)
·如何调整 Redis 内存 (2025-12-26 18:20:07)
·MySQL 数据类型:从 (2025-12-26 18:20:03)
·Linux Shell脚本教程 (2025-12-26 17:51:10)
·Qt教程,Qt5编程入门 (2025-12-26 17:51:07)