【算法】扩展欧几里得算法
一、欧几里得算法
我们前面学过求最大公约数的算法：欧几里得算法（又叫辗转相除法） ，一般缩写是gcd，在C++中经常写成如下形式：
int gcd(int a,int b)
{
if(a%b==0)
return b;
else
return gcd(b,a%b);
}原理就是代码中比较核心的 gcd(b，a%b)，这个定理用文字描述就是:
用a除以b（这里是a>b,当然，在程序编程中，求两个数的最大公约数，可以不限a和b的大小，a<b也就是多一次循环）得到结果q和余数r，再用除数b除以余数r 再得到一个余数，再用除数除以余数，…如此循环，直到余数为0，那么此时的除数就是最大公因数。
想要证明gcd(a,b) = gcd(b,a%b)，需要简单了解下面两个引理：
若d是a和b的公约数，那么d也是b和c的公约数（c为a%b）
若d是b和c的公约数（c为a%b），那么d也是a和b的公约数
这两个引理的是什么意思呢，拿第一个来说；
假设一个数d是a的因子，也就是a=m*d，同时也是b的因子，b=n*d，那么a%b = a-w*b = (m-w*n)*d；
由此可得，a的因子集合、b的因子集合和c的因子集合是相同的；
然后利用上述定理当余数为0的时候，除数就是最大公约数；
二、扩展欧几里得算法
从字面上看，扩展欧几里得算法就是把欧几里得算法进行了扩展，不仅能求a和b的最大公约数，还其他功能，比如:
求ax+by=m的任意一组解，最小整数解。
求模逆元（模反元素）
为了了解学习上面的公式，需要先了解一个裴属定理
【裴属定理】:
对于任意正整数a,b，必有非零整数x,y，使得 ax+by= d。其中，d=gcd(a,b)。
显然有 ax` + by` = k * d ，即 x` =k * x , y`= k* y 。
简言之：ax+by能够取到a和b的最大公约数的整数倍。
简单推论：
如果 a,b互质，即gcd(a,b)=1,则ax+by可以取到任意正整数。
知道了上面的定理，我们求ax+by=m就可以判断是否有解，如果有解，那么m一定是gcd的若干倍。
那么，参考的代码模板如下：
C语言版：
int gcdEx(int a,int b,int*x,int*y)
{
if(b==0)
{
*x=1,*y=0 ;
return a ;
}
else
{
int r=gcdEx(b,a%b,x,y);
/* r = GCD(a, b) = GCD(b, a%b) */
int t=*x ;
*x=*y ;
*y=t-a/b**y ;
return r ;
}
}C++版：
// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1; y = 0;
return a; //到达递归边界开始向上一层返回
}
int d = exgcd(b, a % b, x, y);
int temp=y;
y=x-(a/b)*y;
x=temp;
return d;
}上面的这段代码的解释是：
首先，当递归到达边界时，余数b==0，除数a就是最大公约数，此时可以得出方程的一组解：
x=1, y=0 // a*1+b*0= gcd(a,b)
注意在递归中永远都是先得到上一层的结果状态。
假设栈中当前层得到的解是x1,y1, 那么我们递归后带入下一层:
b*x1 + (a%b)*y1 = gcd(a,b) -> b*x1 + (a- (a/b)*b ) *y1 =gcd(a,b) -> a*y1 + b*(x1- (a/b) *y1) =gcd(a,b)
显然，由上一层的解x1,y1，可以推出下一层x，y的状态
x=y1 y=x1-（a/b）*y1
通解形式：
x=x0+b/gcd(a,b) * n (相当于x每次可以增减：b/gcd的整数倍)
y=y0+a/gcd(a,b) * n (相当于y每次可以增减：a/gcd的整数倍) 《注意：x求出来后，y通常由x代入方程求得》
最小正整数解：
x=(x+b/gcd*n)%(b/gcd) = x%(b/gcd) （b/gcd(a,b)应取正）
若x<=0，则x+=b/gcd
应用：
解不定方程
求逆元
求解线性同余方程
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
