扩展欧几里得算法总结和例子扩展欧几里得算法总结和例子

扩展欧几里得算法即如果a、b是整数，那么一定存在整数x、y使得ax+by=gcd(a,b)
换句话说，如果ax+by=m有解，那么m一定是gcd(a,b)的若干倍。（可以来判断一个这样的式子有没有解）
若gcd(a,b) | c,则方程有解，否则无解。

int gcd(int a,int b)//求a和b的最小公约数 { return b==0?a:gcd(b,a%b); //或者： int gcd(int a,int b) { int c; while(a%b!=0) { c=a%b; a = b; b = c; } return b; }

扩展欧几里得递归结束的条件：当到达递归边界的时候，b==0，a=gcd(a,b) 这时可以观察出来这个式子的一个解：a1+b0=gcd(a,b)，x=1,y=0，注意这时的a和b已经不是最开始的那个a和b了，所以我们如果想要求出解x和y，就要回到最开始的模样
（注意在递归算法中，永远都是先得到下面一个状态的值）
首先我们知道：a%b=a-(a/b)b；带入：
bx1 + (a-(a/b)b)y1
= bx1 + ay1 – (a/b)by1
= ay1 + b(x1 – a/by1) = gcd 发现 x = y1 , y = x1 – a/b*y1
解法：
先运用扩展欧几里得算法求出ax + by = gcd(a,b) 一组特解x0,y0则通解：
x = x0 + b/gcd(a,b) * t
y = y0 - a/gcd(a,b) * t
对应方程 ax + by = c只需要在通解基础上乘以一个比例系数：c/gcd(a,b)
例如：3x+4y=2
利用exgcd算出3x+4y=gcd(3,4)的解x=-1,y=1;
则原式的解为x2/gcd(3，4),y2/gcd(3,4);
求最小正整数解:
使用拓展欧几里德找到ax+by=c的一组整数解(x0,y0)之后，
令k=b/gcd(a,b)，x’=(x0%k+k)%k，y’=(c-ax)/b，就可以得到x的最小正整数解。
同理，令k=a/gcd(a,b)，y’=(y0%k+k)%k，x’=(c-by)/a，就可以得到y的最小正整数解。
解模线性方程
ax ≡ b (mod p)
先对方程进行转换 (ax - b) = -yp 根据同余的性质ax与b的差是模数的倍数
移项可知： ax + py = b

#include #include #include using namespace std; int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法ax+by=c; { if(b==0) { x=1; y=0; return a; //到达递归边界开始向上一层返回 } int r=exgcd(b,a%b,x,y); int temp=y; //把x y变成上一层的 y=x-(a/b)*y; x=temp; return r; //得到a b的最大公因数 } //返回的是a和b的最小公倍数 //而x和y的值则直接得到改变 //而且根据公式可以得到通解 //x = x0 + b*t； //y = y0 - a*t；（t为任意常数）

【扩展欧几里得算法总结和例子】遇到的方程的格式可能不适用于欧几里得算法，需要我们自己移项
例如：（x+mt）-（y+nt）=kl
移项并合并同类项：
（x-y）+（m-n）t=kl
再移项，变为扩展欧几里得的一般形式：
kl+（n-m）*t = x-y
我们和一般形式对比一下，得a=l，b=（n-m），x1=k，y1=t，d=x-y
这里要注意，设c=GCD（a，b），扩展欧几里得有解的条件是d % c== 0，而后面这个x-y不一定是c的倍数。
例题：https://blog.csdn.net/wyg1997/article/details/52085958