当前位置 博文首页 > 文章内容

    HDU2104 - hide handkerchief - gcd辗转相除法

    作者: 栏目:未分类 时间:2020-09-09 16:00:45

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    题意

    给出一个N和M,输入-1 -1结束。
    N代表N个人,Haha开始围绕这N个人丢手绢,每次丢在间隔为M-1的人身边,比如M=2,那么Haha从扔给A,下一次就应该扔给C。
    如果每个人全部都能被丢到一次,那么输出“YES”,否则输出“POOR Haha”。

    思路

    如果N和M不存在公因数,即__gcd(N,M)==1 的时候,输出YES即可。
    画个图自己举个例子就能明白了。

    AC代码

    //#include<bits/stdc++.h>
    #include<iostream>
    #include<string.h>
    #include<algorithm>
    #include<stdio.h>
    #include<cmath>
    #include<list>
    #include<stdlib.h>
    #include<map>
    #include<stack>
    #include<stdio.h>
    #include<queue>
    using namespace std;
    typedef long long ll;
    #define sc(T) scanf("%d",&T)
    #define scc(x,y) scanf("%d %d",&x,&y)
    #define pr(T) printf("%d\n",T)
    #define f(a,b,c) for (int a=b;a<=c;a++)
    #define ff(a,b,c) for (int a=b;a>=c;a--)
    #define inf 0x3f3f3f3f
    #define mem(a,b) memset(a,b,sizeof(a))
    #define eps 1e-9
    #define PI acos(-1)
    
    int main()
    {
        int x,y;
        while(~scc(x,y))
        {
            if(x==-1&&y==-1)
                break;
            if(__gcd(x,y)==1)
                cout<<"YES"<<endl;
            else
                cout<<"POOR Haha"<<endl;
        }
        return 0;
    }