首页 / 算法 / [数论]拓展欧几里得算法
[数论]拓展欧几里得算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[数论]拓展欧几里得算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4107字，纯文字阅读大概需要6分钟。
内容图文
欧几里得算法（辗转相除法）
用来求解最大公约数
1 int gcd(int a,int b){
2 return b ? gcd(b,a%b) : a;
3 }
在 #include<algorithm> 中也可以直接调用 __gcd(a,b)
拓展欧几里得算法
求解不定方程：
引理：存在 x , y 使得 gcd(a,b)=ax+b
1 typedef long long ll;
2
3 ll exgcd(ll a,ll b)
4 {
5 if(b){
6 ll r=exgcd(b,a%b);
7 ll k=x;
8 x=y;
9 y=k-a/b*y;
10 return r;
11 }
12 else{
13 x=1,y=0;
14 return a;
15 }
16 }
解线性同余方程
关于 x 的模方程 ax%b=c 的解，方程转换为 ax+by=c 其中 y 一般为非正整数，则问题变为用 exgcd 解不定方程
计算乘法逆元
若 a*x≡1(mod b) ，且 a与 b互质，那么我们就能定义: x为 a的逆元
这就是利用拓欧求解线性同余方程 a*x≡c(mod b) 的 c=1 的情况。我们就可以转化为解 a*x + b*y = 1这个方程
1 typedef long long ll;
2
3 void exgcd(ll a,ll b)//扩展欧几里得算法求乘法逆元，x为a的逆元
4 {
5 if(!b){
6 x=1,y=0;
7 return;
8 }
9 exgcd(b,a%b);
10 ll k;
11 k=x;
12 x=y;
13 y=k-(a/b)*y;
14 }
一些例题
zoj 3609
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 ll gcd;
5
6 ll exgcd(ll a,ll b,ll &x,ll &y)
7 {
8 if(b==0){
9 x=1,y=0;
10 return a;
11 }
12 ll ans=exgcd(b,a%b,x,y);
13 ll temp=x;
14 x=y;
15 y=temp-a/b*y;
16 return ans;
17 }
18
19 ll cal(ll a,ll b,ll c)
20 {
21 ll x,y;
22 gcd=exgcd(a,b,x,y);
23 ll ans=(x%b+b)%b;
24 if(!ans)
25 ans=b;
26 return ans;
27 }
28
29 int main()
30 {
31 ll a,b,t;
32 cin>>t;
33 while(t--){
34 cin>>a>>b;
35 ll ans=cal(a,b,1);
36 if(gcd!=1)
37 cout<<"Not Exist\n";
38 else
39 cout<<ans<<endl;
40 }
41 return 0;
42 }
zoj 3593
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 ll x,y;
5
6 ll exgcd(int a,int b){
7 if(b){
8 ll n=exgcd(b,a%b);
9 ll xt=x;
10 x=y,y=xt-a/b*y;
11 return n;
12 }
13 x=1,y=0;
14 return a;
15 }
16
17 int main(){
18 ll n,m,t,a,b,c;
19 cin>>t;
20 while(t--){
21 cin>>n>>m>>a>>b;
22 c=n-m;
23 ll ans=exgcd(a,b);
24 if(c%ans!=0){
25 cout<<-1<<endl;
26 continue;
27 }
28 c/=ans,a/=ans,b/=ans;
29 x*=c,y*=c;
30 ll k=(y-x)/(a+b);
31 ans=10000000000ll;
32 for(ll i=k-1;i<k+2;i++){
33 ll xx;
34 ll x0=x+b*i,y0=y-a*i;
35 if(x0<=0&&y0>=0||y0<=0&&x0>=0)
36 xx=abs(x0)+abs(y0);
37 else
38 xx=max(abs(x0),abs(y0));
39 if(xx<ans)
40 ans=xx;
41 }
42 cout<<ans<<endl;
43 }
44 return 0;
45 }
poj 1061
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 typedef long long ll;
5 ll x,y;
6
7 ll exgcd(ll a,ll b)
8 {
9 if(b){
10 ll r=exgcd(b,a%b);
11 ll k=x;
12 x=y;
13 y=k-a/b*y;
14 return r;
15 }
16 else{
17 x=1,y=0;
18 return a;
19 }
20 }
21
22 int main()
23 {
24 ll p,q,m,n,l;
25 scanf("%lld%lld%lld%lld%lld",&p,&q,&m,&n,&l);
26 ll a=n-m,b=l,c=p-q;
27 ll ans=exgcd(a,b);
28 if(c%ans)
29 printf("Impossible\n");
30 else{
31 ll k=c/ans,t=b/ans;
32 x*=k;
33 if(t<0)
34 t=-t;
35 x=(x%t+t)%t;
36 cout<<x<<endl;
37 }
38 return 0;
39 }
hdu 1576
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 typedef long long ll;
5 ll x,y;
6
7 ll exgcd(ll a,ll b)
8 {
9 if(b){
10 ll r=exgcd(b,a%b);
11 ll k=x;
12 x=y;
13 y=k-a/b*y;
14 return r;
15 }
16 else{
17 x=1,y=0;
18 return a;
19 }
20 }
21
22 int main()
23 {
24 ll p,q,m,n,l;
25 scanf("%lld%lld%lld%lld%lld",&p,&q,&m,&n,&l);
26 ll a=n-m,b=l,c=p-q;
27 ll ans=exgcd(a,b);
28 if(c%ans)
29 printf("Impossible\n");
30 else{
31 ll k=c/ans,t=b/ans;
32 x*=k;
33 if(t<0)
34 t=-t;
35 x=(x%t+t)%t;
36 cout<<x<<endl;
37 }
38 return 0;
39 }
内容总结
以上是互联网集市为您收集整理的[数论]拓展欧几里得算法全部内容，希望文章能够帮你解决[数论]拓展欧几里得算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。