杭电ACM 2104:hide handkerchief |解决

1,361次阅读
没有评论

1、原题描述:

杭电ACM

/>

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;
}

总结:

学习了辗转相除法,以及求最大公约数的算法。

参考文章:

https://blog.csdn.net/a22222259/article/details/93515674

https://zhuanlan.zhihu.com/p/31824895

2
西园公子
版权声明:本站原创文章,由西园公子2021-02-02发表,共计648字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
载入中...