2018-07-07-最大公约数
2018-07-07 本文已影响0人
termanary
题目： 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;
}
