首先是我们常用的最大公约数
int gcd(int a,int b)
{
if(b==0)return a;
else return gcd(b,a%b);
}
思想就是辗转相除，大数对小数取余，然后余数与较小数继续进行，直到一个为0,为止。
或是非递归。
int gcd(int x, int y){
if (!x || !y) return x > y ? x : y;
for (int t; t = x % y; x = y, y = t);
return y;
}
辗转相除法又称欧几里德算法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数
快速gcd通过减少乘除法以及基于一个这样的事实，若是某一个都是某个基值的整数倍，则他们最大公约数也是某个基值的整数倍。选取该基值为2可以通过位运算以及“降阶”（减少整数的大小）提高速度。
int kgcd(int a,int b){
if(a==0)return b;
if(b==0)return a;
if(!(a&1)&&!(b&1))returnkgcd(a>>1,b>>1)<<1;
else if(!(b&1))return kgcd(a,b>>1);
else if(!(a&1))return kgcd(a>>1,b);
else return kgcd(abs(a-b),min(a,b));
}
扩充欧几里得算法即扩充GCD就是求得x，y使得gcd(a,b)=ax+by（解一定存在的）
int extgcd(int a,int b, int & x, int & y){
if (b == 0) { x=1; y=0; return a; }
int d = extgcd(b, a % b, x, y);
int t = x; x = y; y = t - a / b * y;
return d;
x、y的复制过程就是计算每一步的a’x+b’y=gcd(a’,b’);系数过程
对于每一步，我们有a’=b,b’=a%b;a’x+b’y=gcd(a’,b’)由于b’=a%b=a-a/b*b
所以对于每一步，我们有a'x + b'y = Gcd(a', b') ===>
bx + (a - a / b * b)y = Gcd(a', b') = Gcd(a, b)===>
ay +b(x - a / b*y) = Gcd(a, b)
这样就可以递归回来得到x,y的值