1、原题描述:
2、题目分析:
这个题大致的意思就是,n 个人围成一圈,haha从自己开始,每隔 m-1 个人的找手绢,一直循环找寻,看是否一定找到手绢。能否一定找到手绢,就看是否将所有人都遍历一遍。
按照网上的解法,是只要 m 和 n 是互质的,那么就一定可以将 m 个人都遍历到,也就是一定可以找到手绢。对此这一点我也是没明白,为啥呢?有懂的朋友,欢迎下方留言,谢谢。
判断两个数互质,也就是判断两个数的最大公约数是1,就要用到我们牛叉的辗转相除法:
3、AC代码:
#include<iostream> using namespace std; int loop(int a, int b){ return b?loop2(b, a%b):a; // 三目运算,若不懂,可看下面的loop2,两个函数意思一样 } int loop2(int a, int b){ int r=1; while(r!=0){ r = a%b; a = b; b = r; } return a; } int main(){ int m, n; while(cin>>m>>n){ if ((m==-1) && (n==-1)) break; if(loop(m, n) == 1){ cout<<"YES"<<endl; } else cout<<"POOR Haha"<<endl; } return 1; }
总结:
学习了辗转相除法,以及求最大公约数的算法。
参考文章: