算法复习——扩展欧几里得算法（扩展欧几里得，逆元，整除）

2019-04-13 22:16发布

站内文章 / 模拟电子
13412 0 1732
①欧几里得算法就是求gcd的有趣的辗转相除法，不再赘述啦0v0代码：int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); }②扩展欧几里得算法需要解决这样的问题：两个非0整数a，b，求一组整数解（x,y），使得ax+by=gcd(a,b).（PS：证明之后补上0....0）int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int g=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return g; }③求逆元可以解决这样的问题：设a和m是整数，求a模m的逆元（逆元：设abm都是整数，m>1，有ab模m和1模m相等，它们拥有相同的余数，那么ab互为模m的逆元。也就是说，有两个数的乘积，如果模m后等于1,则它们互为m的逆元）。gcd(a,m)=1有解。即求ax+my=1=gcd(a,m)。代码：ll inverse(ll a,ll m,ll c) { ll x,y; ll g=exgcd(a,m,x,y); if(c%g!=0) return -1; x*=c/g;      m/=g;      if(m<0) m=-m;     ll ans=x%m;     if(ans<=0) ans+=m;     return ans; }接下来给几个例子0V0↓例子1：zoj 3609，传送门：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4712题意：输入一个n，给n组a和m，求每组a模m的最小逆元。吐槽：m=1的情况……窒息了代码：//zoj 3609求最小逆元 #include #include #include #include #include #include #include #include #include #include using namespace std; const int inf=0x3f3f3f3f; int gcd(int a,int b) { if(b==0) return a; else 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 g=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return g; } int inverse(int a,int m) { int x,y; int g=exgcd(a,m,x,y); return (x%m+m)%m; } int main() { int a,m,n,x,y; cin>>n; while(n--) { cin>>a>>m; int ans=exgcd(a,m,x,y); if(m==1) { cout<<1<例子2：hdu 1576，传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1576代码：#include #include #include #include #include #include #include #include #include #include using namespace std; const int inf=0x3f3f3f3f; int gcd(int a,int b) { if(b==0) return a; else 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 g=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return g; } int inverse(int a,int m) { int x,y; int g=exgcd(a,m,x,y); return (x%m+m)%m; } int main() { int t,n,b; cin>>t; while(t--) { cin>>n>>b; int m=9973; int ans=inverse(b,m); ans=ans*n%m; cout<例子3：hdu2668，传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2669模板题0V0代码：#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; ll gcd(ll a,ll b) { if(b==0) return a; else return gcd(b,a%b); } ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } ll g=exgcd(b,a%b,x,y); ll t=x; x=y; y=t-a/b*y; return g; } ll inverse(ll a,ll m) { ll x,y; ll g=exgcd(a,m,x,y); return (x%m+m)%m; } int main() { ll a,m,x,y; while(scanf("%lld %lld",&a,&m)!=EOF) { ll ans=exgcd(a,m,x,y); if(ans!=1||m==1) cout<<"sorry"<例子4：poj1061，传送门：http://poj.org/problem?id=1061代码：#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; ll gcd(ll a,ll b) { if(b==0) return a; else return gcd(b,a%b); } ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } ll g=exgcd(b,a%b,x,y); ll t=x; x=y; y=t-a/b*y; return g; } ll inverse(ll a,ll m,ll c) { ll x,y; ll g=exgcd(a,m,x,y); if(c%g!=0) return -1; x*=c/g; m/=g; if(m<0) m=-m; ll ans=x%m; if(ans<=0) ans+=m; return ans; } int main() { ll a,b,x,y,l; while(scanf("%lld %lld %lld %lld %lld",&x,&y,&a,&b,&l)!=EOF) { ll ans=inverse(a-b,l,y-x); if(ans==-1) cout<<"Impossible"<

热门文章