扩展欧几里德:
在了解扩展欧几里德之前我们应了解gcd,也就是最大公因数的算法
且看下面这段代码
int gcd(int a,int b){
if(b==0) return a;
else return gcd(b,a%b);
}
当然也可以写成更为简单的三目运算符写法,减少代码长度
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
此方法称为辗转相除法
下面进行推理
给出两数 假定 a=16,b=12;
求两数最大公因数
开始模拟运算过程{
b!=0
返回 a=12,b=4;
b!=0
返回 a=4,b=0
b=0
给出a=4
确实为最大公因数
}
那数学的证明过程呢
设 a/b==k....r 由此可得 r=a-k*b;其中a为被除数,b为除数,k为商,r为余数
设c=gcd(a,b)
即c为a和b的最大公因数
我们不妨设a=m*c,b=n*c;
可得式子 r=a-k*b=mc-k*nc=c(m-kn);
然后可列出 gcd(b,r);
所以 r=c(m-kn);
可得 c为r的因数
由反证法可得m-kn与n互质
可得gcd(b,r)=c;
所以 gcd(a,b)=gcd(b,r)
证毕
妙不可言啊~~~妙不可言~~~
那接下来进入正题
扩展欧几里得
算法本身可以用来求解不定方程
也可以拿来求逆元
还可以拿来求解线性同余方程
先介绍第一个用途
1.扩展欧几里得求解不定方程
二元一次不定方程即 ax+by=m;
但我们完全可以把式子变化一下(反正对式子一无所知)
根据百度可得
ax+by=gcd(a,b) 有解，但zkc大佬告诉我们解不唯一
设 ax+by=gcd(a,b)*k
得 ax+by=d, gcd(a,b)|d;
gcd(a,b)|d 表示 d可以整除gcd(a,b);
当x=1,y=0时
a=gcd(a,b);
我们可以靠递归退回x,y到本身
即可得出答案
网上大佬的论证
当 b=0 时，gcd(a,b)=a，此时 x=1 , y=0
当 b!=0 时，
设 ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2
又因 a%b=a-a/b*b
则 ax1+by1=bx2+(a-a/b*b)y2
ax1+by1=bx2+ay2-a/b*by2
ax1+by1=ay2+bx2-b*a/b*y2
ax1+by1=ay2+b(x2-a/b*y2)
解得 x1=y2 , y1=x2-a/b*y2
因为当 b=0 时存在 x , y 为最后一组解
而每一组的解可根据后一组得到
所以第一组的解 x , y 必然存在
代码
void exgcd(int a,int b){
if(b==0){
x=1;
y=0;
return;
}
exgcd(b,a%b);
k=x;
x=y;
y=k-a/b*y;
return;
}
end;
·