四大扩展欧几里得算法
扩展欧几里得算法1.ax+by=gcd(a,b)
扩展欧几里得算法来解决这样一个问题：给定两个非零整数a和b，求一组整数解(x,y),使得ax+by=gcd(a,b)成立，其中gcd(a,b)表示a和b的最大公约数。
gcd(a,b)–>gcd(b,a%b)–>…..—>gcd(a,0)最终返回a的值，所以就有一组解成立，a*1+b*0=gcd。此时有x=1,y=0
利用上面的式子反推最原始的x和y。
当计算gcd(a,b),有ax1+by1=gcd成立；下一步计算gcd(b,a%b)时，有bx2+(a%b)y2=gcd成立。
因此ax1+by1=bx2+(a%b)y2成立，化简后
x1=y2
y1=x2-(a/b)y2
因此就有啦如下代码：
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法 { if(b==0) { x=1;y=0; return a; //到达递归边界开始向上一层返回 } int r=exgcd(b,a%b,x,y); int temp=x; x=y; //把x y变成上一层的 y=temp-(a/b)*y; return r; //得到a b的最大公因数 }
得到最原始的解后，就可以求全部解
x’=x+(b/gcd)*k
y’=y+(a/gcd)*k
最小非负整数解：(x%(b/gcd)+b/gcd)%(b/gcd)
例题：https://www.acwing.com/problem/content/879/
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法 { if(b==0) { x=1;y=0; return a; //到达递归边界开始向上一层返回 } int r=exgcd(b,a%b,x,y); int temp=x; x=y; //把x y变成上一层的 y=temp-(a/b)*y; return r; //得到a b的最大公因数 } int main() { int a,b,x,y,r,t; cin>>t; while(t--) { cin>>a>>b; r=exgcd(a,b,x,y); cout<<x<<" "<<y<<endl; } return 0; }
如果ax+by=1时，x的最小非负整数就是：(x%b+b)%b
扩展欧几里得算法2.ax+by=c求解
已知ax+by=gcd的解，那么两边同时乘上c/gcd，即为ax+by=c的解
因此（x,y）=(cx0/gcd,cy0/gcd),这样做的充分条件是c%(gcd(a,b))==0
通解：
cx0/gcd+b/gcd*k
cy0/gcd-a/gcd*k
那么他的最小整数解为：
x=((cx/gcd)%(b/gcd)+b/gcd)%(b/gcd)
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法 { if(b==0) { x=1;y=0; return a; //到达递归边界开始向上一层返回 } int r=exgcd(b,a%b,x,y); int temp=x; x=y; //把x y变成上一层的 y=temp-(a/b)*y; return r; //得到a b的最大公因数 } int main() { int c,r,a,b,x,y; cin>>a>>b>>c; r=exgcd(a,b,x,y); cout<<(c*x/r%(b/r)+b/r)%(b/r)<<endl; return 0; }
扩展欧几里得算法3.同余式：ax=c(mod m)的求解
ax=c（mod m）= ( ax-c )%m==0
ax-c=my,令Y=-Y，得
ax+my=c,当c%gcd(a,m)==0时成立，才有解。
解的形式为（x,y）=（cx0/gcd(a,m)，cy0/gcd(a,m)）
通解为：
x’=x+m/gcd(a,m)*k
y’=y-a/gcd(a,m)*k
最小正整数解为：x=((cx0/gcd(a,m)%(m/gcd(a,m))+m/gcd)%m/gcd;
例题：线性同余方程https://www.acwing.com/problem/content/880/
#include<iostream> #include<cstdio> #include<cmath> using namespace std; long long gcd(long long a,long long b) { if(b==0) return a; return gcd(b,a%b); } long long exgcd(long long a,long long b,long long &x,long long &y)//扩展欧几里得算法 { if(b==0) { x=1;y=0; return a; //到达递归边界开始向上一层返回 } long long r=exgcd(b,a%b,x,y); long long temp=x; x=y; //把x y变成上一层的 y=temp-(a/b)*y; return r; //得到a b的最大公因数 } int main() { long long a,b,x,y,r,m,k,t; cin>>t; while(t--) { cin>>a>>b>>m; if(b%gcd(a,m)==0) { r=exgcd(a,m,x,y); cout<<(((b*x)/r)%(m/r)+m/r)%(m/r)<<endl; } else cout<<"impossible"<<endl; } return 0; }
扩展欧几里得算法4.逆元的求解以及（b/a）%m的计算
当计算（b/a）%m的值时，我们需要先算出a模m的逆元x，
就有（b/a）%m=（b*x）%m成立
a模m的逆元就是同余式：ax=1（mod m）
如果gcd（a,m）=1，就有解,求出x后，就可以用(x%m+m)%m得到所需要的逆元。
//在a和m互不是质数的情况下：(b/a)%m=(b%(am))/a /*ab=1(mod m); 计算(b/a)%m=(b*x)%m其中x为a模m的逆元 接下来求解ax=1(mod m) 是否有解取决于 1%gcd(a,m)==0 也就是 gcd(a,m)==1则有解。 求出x，在利用(x%m+m)%m)求出最小解 */ #include<iostream> #include<cstdio> #include<cmath> using namespace std; int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法 { if(b==0) { x=1;y=0; return a; //到达递归边界开始向上一层返回 } int r=exgcd(b,a%b,x,y); int temp=x; x=y; //把x y变成上一层的 y=temp-(a/b)*y; return r; //得到a b的最大公因数 } int main() { int a,b,x,y,m,r; cin>>a>>b>>m; r=exgcd(a,m,x,y); x=(x%m+m)%m; cout<<(b*x)%m<<endl; return 0; }
当然也可以使用费马小定理：am-2%m 就是a模m的逆元，再用快速幂即可求解
例题：快速幂求逆元https://www.acwing.com/problem/content/878/
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll t,a,p; ll gcd(ll a,ll b) { if(b==0) return a; return gcd(b,a%b); } ll qpow(ll n,ll x) { ll ans=1; while(x) { if(x&1) ans=ans*n%p; n=n*n%p; x>>=1; } return ans; } int main() { ll i,j; cin>>t; while(t--) { cin>>a>>p; if(gcd(a,p)==1) cout<<qpow(a,p-2)%p<<endl; else cout<<"impossible"<<endl; } return 0; }
如果a和m互不质，可以用公式(b/a)%m=(b%(a*m))/a
证明：存在整数k，使得b/a=km+x，两边同时乘以a，得b=kam+ax，于是b%（am）=ax，两边同时除以a得，(b%(a*m))/a=x，于是等式成立
注意：a和m的乘积可能太大而溢出。
2019.7.27 扩展欧几里得算法的理解