题目来源HDU - 2104
一道判断互质的题目
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,m.共有n个人,Haha每隔m-1个人查找一次，问经过无数次循环后，Haha是否可以遍历所有人，若可以输出YES,否则输出NO。
起初的思路为计算第一次完成一次循环后，Haha所寻找人的序号作为flag1.然后对一次完整的循环所有序号与该序号对比，若相等则表示只能在几个人之间循环，无法遍历所有人，否则可以。
思路完全是通过找规律找到的，没有证明思路的正确性。后来上网查需要证明n和m两个数互质，即n和m最大公约数为1
因为每次循环遍历的人的序号一定是n和m最大公约数的倍数。所以只要满足最大公约数为1，即可遍历所有人。
判断互质的方法为辗转相除法
互质数定义：
- 两个数的公因数只有1的两个非零自然数,叫做互质数。
- 多个数的若干个最大公因数只有1的正整数，叫做互质数
- 两个不同的质数，为互质数
- 1和任何自然数互质。
- 任何相邻的两个数互质。
具体代码如下：
#include<stdio.h>
int main()
{
long long n,m;
while (scanf("%lld %lld", &n, &m) && n != -1 && m != -1)
{
//确保n最大
if (n < m)
{
n = m + n;
m = n - m;
n = n - m;
}
while (n%m!=1)
{
if (n%m == 0) //n是m的倍数
break;
else
{
n = n%m;
n = n + m;
m = n - m;
n = n - m;
}
}
if (n%m==0)
{
printf("POOR Haha\n");
}
else
{
printf("YES\n");
}
}
return 0;
}
ACM新手，如有说错或可以改进的地方请大家不吝赐教！
网友评论