1.概述
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： gcd函数就是用来求(a,b)的最大公约数的。 gcd函数的基本性质： gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|) 2.原理 设两数为a、b(a>b)，用gcd(a,b)表示a，b的最大公约数，r=a (mod b) ，k=a/b（整除），即a÷b=k.......r。 1：令c=gcd(a,b)，则设a=mc，b=nc // 因为c是最大公约数 2：根据a÷b=k.......r，可列k*b+r=a，代入a，b，解得r=c*（m-n*k） 3：由2可知c是r的一个因数。 4：可以断定m-kn与n互质(假设m-kn=xd，n=yd (d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)cd，b=nc=ycd，则a与b的一个公约数cd>c，故c非a与b的最大公约数，与前面结论矛盾)，因此c也是b与r的最大公约数。 从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。 证毕。 以上步骤的操作是建立在刚开始时r≠0的基础之上的。即m与n亦互质。 当r=0时，c=min(a，b). 代码如下：
int gcd(int a,int b){if(b==0) return a;else return gcd(b,a%b);}
3.拓展欧几里德算法(Extra Euclidean algorithm)
现在我们知道c=gcd(a,b),那么对于a*x+b*y=c的不定方程，我们一定能找到一组特殊解(x0,y0)，使得a*x+b*y=c成立、
x = x0 + (b/gcd)*ty = y0 - (a/gcd)*t
具体的原因可以去了解下贝祖等式
同时，我们也可以列出：
b*x1 + (a%b)*y1 = gcd
我们知道： a%b = a - (a/b)*b（'/'整除）
那么，我们可以进一步得到：
gcd = b*x1 + (a-(a/b)*b)*y1
= b*x1 + a*y1 – (a/b)*b*y1
= a*y1 + b*(x1 – a/b*y1)
x = y1y = x1 – a/b*y1
有了递推式，就可以形成递归
int exgcd(int a,int b,int &x,int &y){int ans,temp;if(b==0){x=1;y=0;return a;}ans=exgcd(b,a%b,x,y);temp=x;x=y;y=temp-a/b*y;return ans;}
更多拓展的内容可以参考：/yo_joker/article/details/52578174
