歐幾里得算法 這個就是常說的輾轉相除法，用于計算兩個整數 $a,b$ 的最大公約數，即$$gcd(a,b)=gcd(b,a\;mod\;b)$$

int gcd(int a,int b){return b==0 ? a : gcd(b,a%b); } View Code

　　擴展歐幾里德算法?是用來在已知 $a,b$ 求一組整數解 $x,y$ 使它們滿足等式$$ax+by=gcd(a, b)$$

　　（解一定存在 根據數論中的相關定理?具體怎么證明我也不清楚）

　　那么問題來了 如何求出一組 $x,y$?

　　證明如下（重點）：

　　設 $a>b$

?　　顯然當 $b=0$ , $gcd(a,b)=a$ 時，$x=1$ , $y=0$ ；

　　當 $a>b>0$ 時，設$$ax_1+by_1= gcd(a,b)$$$$bx_2+(a\;mod\;b)y_2=gcd(b,a\;mod\;b)$$

　　根據樸素的歐幾里得算法，可得$$ax_1+by_1=bx_2+(a\;mod\;b)y_2$$$$ax_1+by_1=bx_2+(a- \lfloor?\frac{a}{b} \rfloor b)y_2$$$$ax_1+by_1=ay_2+b(x_2- \lfloor?\frac{a}{b}?\rfloor y_2)$$

　　根據恒等定理得$$x_1=y_2$$$$y_1=x_2- \lfloor \frac{a}{b} \rfloor y_2$$

　　這樣我們就得到了求解 $x_1,y_1$ 的方法：$x_1,y_1$ 的值基于 $x_2,y_2$

　　上面的思想是以遞歸定義的，因為 $gcd$ 不斷的遞歸求解一定會有個時候 $b=0$ ，所以遞歸可以結束

int exgcd(int a,int b,int &x1,int &y1){if(!b){x1=1;y1=0;return a;}ans=exgcd(b,a%b,x1,y1);int t=x1;x1=y1;y1=t-a/b*y1;return ans; } View Code

?　　下面是一些重要的結論

　　結論一?設 $a,b,c$ 為任意整數，若方程 $ax+by=c$?的一組整數解為 $(x_0,y_0)$ ，則他們的任意整數解都可以寫成 $(x_0+kb',y_0-ka')$ ，其中 $a'=\frac{a}{gcd(a,b)}$ ,?$b'=\frac{b}{gcd(a,b)}$ , $k \in Z$

　　結論二?設 $a,b,c$ 為任意整數，$g=gcd(a,b)$ ，方程 $ax+by=g$?的一組整數解為 $(x_0,y_0)$ ，則當 $c$ 是 $g$ 的倍數時，$ax+by=c$ 的一組整數解是 $(x_0 \frac{c}{g},y_0 \frac{c}{g})$ ；當 $c$ 不是 $g$ 的倍數時，無整數解

?

　　然后洛谷上有道關于擴展歐幾里得很經典的題 青蛙的約會 下面是AC代碼

#include <cstdio> #include <algorithm> using namespace std; #define ll long longll x,y,m,n,l; ll ans,x1,y1;ll exgcd(ll a,ll b,ll &x1,ll &y1){if(!b){x1=1;y1=0;return a;}ans=exgcd(b,a%b,x1,y1);ll t=x1;x1=y1;y1=t-a/b*y1;return ans; }int main(){scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);ll a=n-m,c=x-y;if(a<0){a=-a;c=-c;}exgcd(a,l,x1,y1);if(c%ans) printf("Impossible");else printf("%lld",((x1*(c/ans))%(l/ans)+(l/ans))%(l/ans));//處理負數的神奇方法 return 0; } View Code

?

轉載于:https://www.cnblogs.com/Pedesis/p/10339787.html

總結

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

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