200字范文 > 欧几里得算法和扩展欧几里得算法(Euclidean_Algorithm and Extended_Euclidean_Algorithm)

欧几里得算法和扩展欧几里得算法(Euclidean_Algorithm and Extended_Euclidean_Algorithm)

时间：2019-09-12 08:29:17

一、基本概念

欧几里得算法：又名辗转相除法，计算两个整数a,b的最大公约数。

扩展欧几里得算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

二、基本性质

gcd函数的基本性质：gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)

贝祖定理：即如果a、b是整数，那么一定存在整数x、y使得ax+by=gcd(a,b)。

三、算法

欧几里得算法

gcd(a,b) = gcd(b,a mod b)

证明：
将a表示为a=kb+r，则r=a%b,r=a-kb；
假设d为a,b的一个公约数，则a%d=0,b%d=0,又r=a-kb，所以r%d=0;
整理下：b%d=0，r%d=0（(a%b)%d=0）
即d也是b和a%b的公约数，所以a和b的最大公约数也是b和a%b的最大公约数。

扩展欧几里得算法

已知：a%b=a-(a/b)*b

b*x1 + (a-(a/b)*b)*y1

= b*x1 + a*y1 – (a/b)*b*y1

= a*y1+ b*(x1 – a/b*y1)=gcd

证明：
假设a>b,
(1)b=0gcd(a,b)=a,ax=a,则x=1，y=0;（这里我还是推荐不把gcd(a,0)理解成最大公约数，而是一个计算机求出来的值）
(2)假设ax1+by1=gcd(a,b)(方程一)bx2+(a%b)y2=gcd(b,a%b)（方程二）;由欧几里得算法gcd(a,b)=gcd(b,a%b)得到，
ax1+by1=bx2+(a%b)y2，即ax1+by1=bx2+(a-a/b*b)y2ax1+by1=ay2+b(x2-a/b*y2)

四、代码

欧几里得算法

C++版本一

1. 若 r 是 a ÷ b 的余数, 则

gcd(a,b) = gcd(b,r)

2. a 和其倍数之最大公因子为 a。

#include<iostream>using namespace std;int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}int main(){int a,b;cout<<"Please enter two integers:"<<endl;cin>>a>>b;cout<<a<<" and "<<b<<"'s gcd is："<<endl;cout<<gcd(a,b)<<endl;return 0;}

C++版本二

1. a ÷ b，令r为所得余数（0≤r＜b）

若 r = 0，算法结束；b 即为答案。

2. 互换：置 a←b，b←r，并返回第一步。

#include<iostream>using namespace std;int gcd(int a,int b){int temp;while(b!=0){temp=b;b=a%b;a=temp;}return a;}int main(){int a,b;cout<<"Please enter two integers:"<<endl;cin>>a>>b;cout<<a<<" and "<<b<<"'s gcd is："<<endl;cout<<gcd(a,b)<<endl;return 0;}

扩展欧几里得算法

C++版本一

#include<iostream>using namespace std;int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int gcd=exgcd(b,a%b,x,y);int x2=x,y2=y;x=y2;y=x2-(a/b)*y2;return gcd;}int main(){int x,y,a,b;cout<<"请输入a和b:"<<endl;cin>>a>>b;cout<<"a和b的最大公约数:"<<endl;cout<<exgcd(a,b,x,y)<<endl;cout<<"ax+by=gcd(a,b) 的一组解是:"<<endl;cout<<x<<" "<<y<<endl;return 0;}

C++版本二

#include<iostream>using namespace std;int exgcd(int a,int b,int &x,int &y){int x1,y1,x0,y0;x0=1; y0=0;x1=0; y1=1;x=0; y=1;int r=a%b;int q=(a-r)/b;while(r){x=x0-q*x1; y=y0-q*y1;x0=x1; y0=y1;x1=x; y1=y;a=b; b=r; r=a%b;q=(a-r)/b;}return b;}int main(){int x,y,a,b;cout<<"请输入a和b:"<<endl;cin>>a>>b;cout<<"a和b的最大公约数:"<<endl;cout<<exgcd(a,b,x,y)<<endl;cout<<"ax+by=gcd(a,b) 的一组解是:"<<endl;cout<<x<<" "<<y<<endl;return 0;}