杭电OJ 2104. hide handkerchief

题目描述：

Problem Description

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".

Input

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.

Output

For each input case, you should only the result that Haha can find the handkerchief or not.

Sample Input

3 2

-1 -1

Sample Output

YES

思路：

该题目的大体意思是，有N个人参加了“找手绢”游戏。N个人围成一个圆圈，手绢就藏在其中某一个人的手里，哈哈同学负责找手绢。哈哈同学找手绢有个习惯，就是心中默想一个数M，检查完一个人后，就检查其之后的第M-1个人，直至找到手绢。给你一组N，M的组合，问你哈哈同学能否成功找到手绢。

读完这个题我也是一阵懵逼，最后参考了别人的答案。

如果哈哈同学能够按照他的方法找到手绢，则需要N个人都被访问，这就要求N和M互质，即N和M的最大公因数为1，否则N位同学中必有一些人不被访问，导致哈哈同学找不到手绢。

（证明就略了，数学太菜）

问题的关键就是看N和M的最大公因数是否为1，这里介绍“辗转相除法”。

辗转相除法：求两个数N和M的最大公因数 （1）先将大数N除以小数M，取余； （2）如果余数为0，则小数M为两个数的最大公因数；如果余数不为0，则将小数M除以该余数，继续取余； （3）如果新的余数为0，则上一个余数为原来两个数的最大公因数；如果新的余数不为0，则将上一个余数除以该新的余数，继续取余； （4）重复第（3）步，直到新的余数为0 ，此时的上一个余数就是原来两个数N和M的最大公因数

实现（C++）：

#include <iostream>
using namespace std;

int main(){
	
	int N, M;
	while(cin>>N>>M){
		
		if(N==-1&&M==-1)
			break;
			
		while(M!=0){
			int temp=M;
			M=N%M;
			N=temp;
		}
		
		if(N!=1)
			cout<<"POOR Haha"<<endl;
		else
			cout<<"YES"<<endl;
	}
	
	return 1;
}

学好算法需要强大的数学思维能力与扎实的数学基础