基础数论--扩展欧几里得算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了基础数论--扩展欧几里得算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1978字，纯文字阅读大概需要3分钟。

内容图文

正常的欧几里得算法

1 int gcd(int a,int b){
2     return b==0?a:gcd(b,a%b);
3 }

可以在O(n)的时间复杂度内，求出a和b两数的最大公约数。

而扩展欧几里得算法则可以在求出最大公约数的同时，求出两个数x，y，使得x*a+y*b=gcd(a,b)，用处就是可以用来求解线性同余方程（写在下边）

 1 //推荐第二种写法
 2 #include<iostream>
 3 using namespace std;
 4 int exgcd1(int a,int b,int& x,int& y){
 5     if(b==0){
 6         x=1,y=0;
 7         return a;
 8     }else{
 9         int d=exgcd1(b,a%b,x,y);
10         int t=y;
11         y=x-(a/b)*y;
12         x=t;
13         return d;
14     }　　
15 }
16 int exgcd2(int a,int b,int& x,int& y){
17     if(b==0){
18         x=1,y=0;
19         return a;
20     }else{
21         int d=exgcd2(b,a%b,y,x);
22         y=y-(a/b)*x;
23         return d;
24     }
25 }
26 int main(void){
27     int n;
28     cin>>n;
29     for(int i=0;i<n;i++){
30         int a,b,x,y;
31         cin>>a>>b;
32         exgcd2(a,b,x,y);
33         cout<<x<<" "<<y<<endl;
34     }
35     return 0;
36 }

第一种证明，第二种类似

 

求解同余方程

同余方程的定义，给定a,b,m，求出一个满足条件的x，使得a*x=b(mod m)。

也就是a*x=b+y*m，令y′=-y，得

x*a+ y′ *m=b，这就和上边的扩展欧几里得完全符合

 1 #include<iostream>
 2 using namespace std;
 3 typedef long long LL;
 4 int exgcd(int a,int b,int& x,int& y){
 5     if(b==0){
 6         x=1,y=0;
 7         return a;
 8     }else{
 9         int d=exgcd(b,a%b,y,x);
10         y=y-(a/b)*x;
11         return d;
12     }
13 }
14 int main(void){
15     int n;
16     cin>>n;
17     for(int i=0;i<n;i++){
18         int a,b,m;
19         int x,y;
20         cin>>a>>b>>m;
21         int d=exgcd(a,m,x,y);
22         if(b%d==0){
23             cout<<(LL)(b/d)*x%m<<endl;//%m是为了保证答案在m的范围内
24                                       //% m 仍然是正确的是因为，相当于将y′增加了
25         }else{
26             cout<<"impossible"<<endl;
27         }
28     }
29     return 0;
30 }

既然能解同余方程的话，那就能够求逆元，只不过逆元是更加特殊的情况，b=1

具体的可以翻一翻博客。

 

内容总结

以上是互联网集市为您收集整理的基础数论--扩展欧几里得算法全部内容，希望文章能够帮你解决基础数论--扩展欧几里得算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---