一、基本概念

歐幾里得算法：又名輾轉相除法，計算兩個整數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=0??gcd(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)y2?ax1+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; }

五、例題

https://codeforces.com/contest/1152/problem/C（題解：https://blog.csdn.net/weixin_43272781/article/details/89513932）

六、參考文章

https://www.cnblogs.com/haveyoueverbeen/p/4502005.html

https://www.cnblogs.com/haveyoueverbeen/p/4612753.html

https://www.cnblogs.com/haveyoueverbeen/p/4612827.html

?

總結

以上是生活随笔為你收集整理的欧几里得算法和扩展欧几里得算法(Euclidean_Algorithm and Extended_Euclidean_Algorithm)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。