数论|欧几里得算法（辗转相除）&扩展欧几里得数论|2018-02-假期训练

欧几里得算法是用来计算两个数的最大公约数；

int GCD(int a, int b)//注意此处a>b; { return b==0?a:gcd(b, a%b); }

应用：
一：最常见的，用来求最小公倍数(LCM)；
LCM=a/GCD(a, b)*b;
二：扩展欧几里得算法，求二元一次方程(a*x+b*y=c)的解;
二元一次方程性质：(a*x+b*y=c)有解(整数解)的充要条件:c|gcd(a, b)(c是a, b的最大公约数的倍数)；

int exgcd(int a, int b, int &x, int &y) { if(b==0){ x=1; y=0; return a; } int r=exgcd(b, a%b, x, y); int t=x; x=y; y=t-a/b*y; return r; }

r表示a, b的最大公约数; x, y为c=gcd(a, b)时的一个解；
a/=r, b/=r;
x+=k*b, y-=k*a(k∈Z)是c=r的通解； d=gcd(a, b);
则a*x+b*y=c的特解:x*=d, y*=d;
a/=r, b/=r;

则通解：x+=k*b, y-=k*a(k∈Z)

【数论|欧几里得算法（辗转相除）&扩展欧几里得】