首页 > ACM题库 > HDU-杭电 > hdu 2104 hide handkerchief[解题报告]C++
2013
12-29

hdu 2104 hide handkerchief[解题报告]C++

hide handkerchief

问题描述 :

The Children’s Day has passed for some days .Has you remembered something happened at your childhood? I remembered I often played a game called hide handkerchief with my friends.
Now I introduce the game to you. Suppose there are N people played the game ,who sit on the ground forming a circle ,everyone owns a box behind them .Also there is a beautiful handkerchief hid in a box which is one of the boxes .
Then Haha(a friend of mine) is called to find the handkerchief. But he has a strange habit. Each time he will search the next box which is separated by M-1 boxes from the current box. For example, there are three boxes named A,B,C, and now Haha is at place of A. now he decide the M if equal to 2, so he will search A first, then he will search the C box, for C is separated by 2-1 = 1 box B from the current box A . Then he will search the box B ,then he will search the box A.
So after three times he establishes that he can find the beautiful handkerchief. Now I will give you N and M, can you tell me that Haha is able to find the handkerchief or not. If he can, you should tell me "YES", else tell me "POOR Haha".

输入:

There will be several test cases; each case input contains two integers N and M, which satisfy the relationship: 1<=M<=100000000 and 3<=N<=100000000. When N=-1 and M=-1 means the end of input case, and you should not process the data.

输出:

There will be several test cases; each case input contains two integers N and M, which satisfy the relationship: 1<=M<=100000000 and 3<=N<=100000000. When N=-1 and M=-1 means the end of input case, and you should not process the data.

样例输入:

3 2
-1 -1

样例输出:

YES

题目大意:意思是n个人围成一个圈,大家玩丢手帕游戏,手帕藏在某一个人的箱子里,Haha来找,每一次他都会跳过m-1个人。问你Haha是不是一定能找到手帕。因为Haha找的次数是无限的,可以永远找下去,所以,只要他能把所有的人都找一遍就一定能找到。但按照他的这种找法,如果nm不互质的话,不互质就会出现某些人是永远不会找。所以看一下 nm的最大公约数就行了


解题思路:

判断是否可以遍历所有的盒子,只要盒子数和每次走的步数存在值不等于1的最大公约数时,他就会回到起点,从而做重复的动作。

归根结底,其实就是给出盒子数和步数,判断能否遍历所有盒子。这里有一个规律就是如果和字数和步数互质(最大公约数为1),那么则能遍历,否则不能遍历。


代码如下:

/*
 * 2014_2.cpp
 *
 *  Created on: 2013年8月10日
 *      Author: Administrator
 */

#include <stdio.h>

/**
 * 辗转相除法,用来求最大公约数
 */
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");
		}
	}
}

解题转自:http://blog.csdn.net/hjd_love_zzt/article/details/9867479


  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!