2018-07-07-最大公约数

题目： Easy Problem

本题等到一个结论，故记下来：

一个数对另一个数的取余：

可以等效为：

任意个乘数(全部相乘必须等于原数)分别取余的余数相乘再取余。

任意个和数(全部相加必须等于原数)分别取余的余数相加再取余。

(数论书本上可能会有，没来得及看，有时间一定补)

代码：

#includeint gcd(int a,int b)

{

    while(b!=0)

    {

        a%=b;

        a=a^b;

        b=a^b;

        a=a^b;

    }

    return a;

}

int mod(int a,int b)

{

    int c=a%b,d=1;

    int ca,da;

    while(a!=0)

    {

        ca=a/3;

        c=c*c*c;

        c%=b;

        da=a%3;

        while(da--)

            d*=d;

        d%=b;

        a=ca;

    }

    return (c*d)%b;

}

int main()

{

    int a,b;

    while(scanf("%d%d",&a,&b)!=EOF)

    {

        b=mod(b,a);

        printf("%d\n",gcd(a,b));

    }

    return 0;

}