杭电ACM-2104

题目：

2104题

#include<stdio.h>
int main()
{
    int n,m,t;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==-1&&m==-1)
            break;
        int flag=0;
        for(;n>0&&m>0;)
        {
            if(n==1&&m==1)
            {
                printf("YES\n");
                flag=1;
                break;
            }
            if(n<m)
            {
                t=n;
                n=m;
                m=t;
            }
            n=n-m;
        }
        if(flag==0)
            printf("POOR Haha\n");
    }
    return 0;
}

此代码运用了更相减损术，通过 两数相减的差 与 被减数 不断相减，直到两数相减的差与被减数相同，即此时这2个数为原来2个数的最大公约数
此题只要2个数互质就可以（互质：即2个数的最大公约数为1）
但是... ...这个方法复杂了

所以换一个方法：（辗转相除法）

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

判断2个数的最大公约数的模版：

int gcd(int a,int b)
{
    if(b==0)return a;
    else return gcd(b,a%b);
} //递归法求最大公约数，当最大公约数是1的时候，两个数互质
    if(gcd(x,y)==1)那么x,y互质

注意：此题题意翻译过来就是两数互质！！！