歐幾里得算法：

int gcd(int x,int y){if(y) return gcd(y,x%y);return x; }

擴展歐幾里得算法：

先說一個整體思路：
先求Ax+By=gcd(A,B);的一個解x，y
然后我們可以求他的通解
然后求Ax+By=C的通解

我們先看看怎么求Ax+By=gcd(A,B);的一個解x，y
設 a>b。
1，顯然當 b=0，gcd（a，b）=a。此時 x=1，y=0；
2，a>b>0 時
設 ax1+ by1= gcd(a,b);
bx2+ (a mod b)y2= gcd(b,a mod b);
根據樸素的歐幾里德原理有 gcd(a,b) = gcd(b,a mod b);
則:ax1+ by1= bx2+ (a mod b)y2;
即:ax1+ by1= bx2+ (a - [a / b] * b)y2=ay2+ bx2- [a / b] * by2;
也就是ax1+ by1 == ay2+ b(x2- [a / b] *y2);

根據恒等定理得：x1=y2; y1=x2- [a / b] *y2;
這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
上面的思想是以遞歸定義的，因為 gcd 不斷的遞歸求解一定會有個時候 b=0，所以遞歸可以結束。

void Ex_gcd(int a, int b, int &x, int &y) {if(b == 0)//遞歸出口{x = 1;y = 0;return;}int x1, y1;Ex_gcd(b, a%b, x1, y1);x = y1;y = x1-(a/b)*y1; }

上面已經列出找一個整數解的方法，我們接下來找通解

取另外一組解（x2，y2）
則ax1+by1=ax2+by2=gcd(a,b)
變形得a(x1-x2)=b(y1-y2)
假設gcd（a,b)=g
方程左右兩邊同時除以g
a’(x1-x2)=b’(y2-y1),a’=a/g,b’=b/g
此時a’和b’互為素數
因此x1-x2一定是b’的整數倍,設為kb’
因此若方程一組整數解為（x0，y0）
他的任意整數解都可寫成
（x0+kb’,y0-ka’）
a’=a/gcd(a,b)
b’=b/gcd(a,b)

結論：在找到Ax+By = Gcd(A, B)的一組解x0,y0后，Ax+By = Gcd(A, B)的其他整數解滿足：
x = x0 + B/Gcd(A, B) * t
y = y0 - A/Gcd(A, B) * t(其中t為任意整數)

明白了原始的Ax+By=gcd(A,B)情況，我們可以擴展到一般的情況，即

Ax+By=C

對于Ax+By=c的整數解，只需將Ax+By = Gcd(A, B)的每個解乘上 C/Gcd(A, B) 即可，
但是所得解并不是該方程的所有解，找其所有解的方法如下：
在找到Ax+By= Gcd(A, B)的一組解x0,y0后，可以
得到Ax+By = C的一組解x1 = x0*(C/Gcd(A,B)),y1 = y0*(C/Gcd(A,B))，Ax+By = C的其他整數解滿足：
x = x1 + B/Gcd(A, B) * t
y = y1 - A/Gcd(A, B) * t(其中t為任意整數)
y就是Ax+By=C的所有整數解。

練習題目：

Now tell you two nonnegative integer a and b. Find the nonnegative integer X and integer Y to satisfy Xa + Yb = 1. If no such answer print “sorry” instead.
Input
The input contains multiple test cases.
Each case two nonnegative integer a,b (0< a, b< =2^31)
Output
output nonnegative integer X and integer Y, if there are more answers than the X smaller one will be choosed. If no answer put “sorry” instead.
Sample Input
77 51
10 44
34 79
Sample Output
2 -3
sorry
7 -3

分析與解答

代碼參考：只有這個代碼才是這個算法的真諦

#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> using namespace std;long long gcd(long long a,long long b){if(!b) return a;return gcd(b,a%b); }void exgcd(long long a,long long &x,long long b,long long &y){if(!b){x=1;y=0;}else{exgcd(b,y,a%b,x);y-=x*(a/b);} } int main(){long long t,A,B,x,y;while(cin>>A>>B){if(gcd(A,B)!=1)cout<<"sorry"<<endl;else{exgcd(A,x,B,y);//已經得到了一個特解xywhile(x<0) {x+=B;y-=A;}//找最小的正整數解cout<<x<<' '<<y<<endl;}}return 0; }

總結

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

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