欧几里得& 拓展欧几里得（Euclid & Extend-Euclid）欧几里得算法（Euclid）背景：
欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。 ——百度百科
代码：
递推的代码是相当的简洁：
int gcd(int a,int b) { return b == 0 ? a : gcd(b, a % b); }分析：
方法说了是辗转相除法，自然没有什么好介绍的了。。
Fresh肯定会觉得这样递归下去会不会爆栈？实际上在这里是不会爆栈的，因为递归的层数是非常小的，不信你可以随便拿一些大数测试一下，lrj的白书和紫书上讲到gcd函数的递归层数不超过40785lgN + 1.6723，其中N=max{a，b}。让gcd函数递归层数最多的是gcd（F(n),F(n-1)），F(n)是Fibonacci数！！至于为什么博主没有证明，有想法的小伙伴麻烦在评论在说下下，(*^__^*) 嘻嘻……
拓展欧几里得（Extend- Euclid）背景：
扩展欧几里德算法是用来在已知a, b求解一组x，y [x,y都是整数]，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。 ——百度百科
用到的几个欧几里得重要结论：
1) gcd(a,b)= gcd(b,a %b);
2) gcd(a,0)= a.
代码：typedef __int64 ll;void exgcd(ll a, ll b, ll& d, ll& x, ll &y){if(!b){d = a, x = 1, y = 0;}else{exgcd(b, a % b, d, y, x);y -= x * (a / b);}}分析：
设如下两个方程：
ax+by = gcd(a,b) = d；
bx’+(a%b)y’ = gcd(b,a%b)；
那么由重要结论（1）有gcd(a,b) = gcd(b,a %b)，
那么ax+by = bx’+(a%b)y’ = bx’ +(a – [a/b]*b)y’ = ay’ + b(x’ – [a/b]y’)，
由恒等关系有： x = y’ , y = (x’ – [a/b]y’)，[a/b]表示a/b的值向下取整。
……..
那么现在就可以用exgcd(a,b,d,x,y)表示方程ax+by = d，，那么由上面一直递归下去，直到 b = 0，递归结束，此时 d = gcd(a,0) =a , x = 1,y =0;【因为 ax+0*y = gcd(a,0)嘛~】
拓展欧几里得的几个应用求解不定方程
例如：求解不定整数方程ax+by = c
求ax+by = c， 令d =gcd(a,b);
那么(a / d ) * x + (b / d )* y = c / d
因为(a / d )、(b / d ) 、x、y都是整数，那么
如果有解，那么令 K = c/d；
那么，对方程aX+bY = d；假设有拓展欧几里得求出一组解为(X0,Y0)，那么aX0+bY0 = d；等式两边同时乘以K，即K*( aX0+bY0 ) = d*K = c；由恒等关系，原方程的解（x0，y0）：
不定方程的通解：
若（x0，y0）是不定整数方程ax+by = c的一组解，则他的任意整数解都可以表示成（x0+ kb’, y0-ka’），其中a’ = a/gcd(a,b), b’ = b/gcd(a,b).
例题：
POJ 1061青蛙的约会 链接: ?id=1061
求解模线性方程
方法跟上面类似，将同余方程转化为常规线性方程就可以了，跟上面一样，谈到同余方程的一个解时，其实指的是一个同余等价类….
具体内容待补充…
求模的逆元
待补充…
版权声明：本文为博主原创文章，未经博主允许不得转载。
偶尔因高山流水的美丽停留，
