杭电 -- 2104

我不是女神ヾ 2021-10-23 18:32 284阅读 0赞

## 引入（辗转相除法） ##

辗转相除法， 又名欧几里得算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

## 题目 ##

![1460404-20190708113222193-1264420750.png][]

## 题意及思路 ##

题目大意：n个小朋友，每个人有一个盒子（其中只有一个盒子有手帕），现在有一个人从当前位置出发（先访问自己的盒子），每隔m个位置访问下一个小朋友的盒子。问？能否找到手帕。

思路：辗转相除法求n和m的最大公约数。（还不懂。。。）

踩坑点：直接暴力法求解，不动脑筋，找不到问题的本质。

## 代码 ##

#include<stdio.h>
    int gcd(int a,int b)
    {
        if(b==0)return a;
        else return gcd(b,a%b);
    } //递归法求最大公约数，当最大公约数是1的时候，两个数互质 a必须要大于b
    
    int main()
    {
        int x,y,t;
        while(~scanf("%d%d",&x,&y))
        {
            if(x==-1&&y==-1)
                break;
            if(y>x)
            {
                t=x;
                x=y;
                y=t;
            }
            if(gcd(x,y)==1)
            {
                printf("YES\n");
            }
            else
            {
                printf("POOR Haha\n");
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/kyrie211/p/11150290.html

[1460404-20190708113222193-1264420750.png]: /images/20211023/298d7500a10f42899232b6207a2c1124.png

发表评论取消回复

表情：

评论列表（有 0 条评论，284人围观）

还没有评论，来说两句吧...

相关阅读

相关杭电1061

Rightmost Digit Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

布满荆棘的人生/ 2022年09月17日 05:27/ 0 赞/ 282 阅读

相关杭电1039

Easier Done Than Said? Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 6553

一时失言乱红尘/ 2022年06月05日 12:48/ 0 赞/ 287 阅读

相关杭电1026

Ignatius and the Princess I Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 6553

快来打我*/ 2022年06月04日 05:53/ 0 赞/ 306 阅读

相关杭电oj

Problem Title 2 Pro. ID 1001 Sum Problem include<stdio.h> int main() {

缺乏、安全感/ 2022年05月15日 16:18/ 0 赞/ 267 阅读

相关杭电oj

Problem Title 1 Pro. ID 1000 A+B Problem include<stdio.h> int main() {

￡神魔★判官ぃ/ 2022年05月15日 16:14/ 0 赞/ 334 阅读

相关杭电1060

此题是一道数学题，也是一道技巧题，也是不能直接算的，否则会超时的！！！此题思路：设n^n=d.xxxx\10^(k-1)，其中k表示n^n的位数； d.xxxx

痛定思痛。/ 2021年12月01日 22:40/ 0 赞/ 326 阅读

相关杭电2075

此题真的是简单的再不能简单了！呵呵！我一直纠结，出这样的题是什么意思呢？不懂！哎，不说那些废话了，直接 ac吧！呵呵！ \include<iostream> using

今天药忘吃喽~/ 2021年12月01日 22:38/ 0 赞/ 310 阅读

相关杭电2078

说实话，此题是一道有严重bug的问题，对于xhd没晚能复习的科目数m根本就没用上！！！哎不管那么些了，反正ac了！呵呵！此题这样想xhd得复习效率是前一课程和后一课程复习效率差

╰+攻爆jí腚メ/ 2021年12月01日 22:38/ 0 赞/ 354 阅读

相关杭电2090

此题就是一道令人无法琢磨的题！哎！！我简直就无语了！！呵呵！竟然能出这题。。。。废话少说，直接ac！！！ \\\ 此题要想输出结果，还需要注意一下！在linux

约定不等于承诺〃/ 2021年12月01日 21:12/ 0 赞/ 368 阅读

相关杭电 -- 2104

引入（辗转相除法）辗转相除法，又名欧几里得算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数

我不是女神ヾ/ 2021年10月23日 18:32/ 0 赞/ 285 阅读