先來看看歐幾里得算法：

1 public class Gcd { 2 /** 3 * 歐幾里德算法,即輾轉(zhuǎn)相除法 最大公約數(shù) 4 */ 5 public static long gcd(long m, long n) { 6 return n == 0 ? m : gcd(n, m % n); 7 } 8 9 /** 10 * 最小公倍數(shù)lowest common multiple (LCM) 11 * 最小公倍數(shù) = a * b / a和b的最大公約數(shù) 12 */ 13 private static long lcm(long a, long b) { 14 return a * b / gcd(a, b); 15 } 16 }

　　接著再來看裴蜀(貝祖)等式：對(duì)于任何整數(shù)a、b和它們的最大公約數(shù)d，關(guān)于未知數(shù)x和y的線性丟番圖方程(稱為裴蜀等式)：ax+by = m 有整數(shù)解時(shí)當(dāng)且僅當(dāng)m是d的倍數(shù)。x、y可用擴(kuò)展歐幾里得算法求得。特別地，方程ax+by=1 有整數(shù)解當(dāng)且僅當(dāng)整數(shù)a和b互質(zhì)。

　　那什么是擴(kuò)展歐幾里得算法呢？

　　現(xiàn)在我們知道了 a 和 b 的最大公約數(shù)是 gcd(a,b) 后面用gcd表示 ，那么，我們一定能夠找到這樣的 x 和 y ，使得: a*x + b*y = gcd 。這是一個(gè)不定方程。那么，怎么求出這個(gè)特解 x 和 y 呢？只需要在歐幾里德算法的基礎(chǔ)上加點(diǎn)改動(dòng)就行了。我們觀察到：歐幾里德算法停止的狀態(tài)是： a= gcd ， b = 0 ，那么，這是否能給我們求解 x y 提供一種思路呢？

　　首先，將a=gcd,b=0代入原方程，得到gcd*x+0*y=gcd。那么，這時(shí)候，只要x = 1 ，y 是 0 或者其他值（無所謂是多少，反正任何數(shù)乘以 0 都等于 0， 但是 x 一定要是 1），這時(shí)，我們就會(huì)有： a*1 + b*0 = gcd。?當(dāng)然這是最終狀態(tài)，但是我們是否可以從最終狀態(tài)反推到最初的狀態(tài)呢？

　　假設(shè)當(dāng)前我們要處理的是求出 a 和 b的最大公約數(shù)，并求出 x 和 y 使得 a*x + b*y= gcd ，而我們已經(jīng)求出了下一個(gè)狀態(tài)：b 和 a%b 的最大公約數(shù)，并且求出了一組x1 和y1 使得： b*x1 + (a%b)*y1 = gcd ， 那么這兩個(gè)相鄰的狀態(tài)之間是否存在一種關(guān)系呢？

　　首先a可以表示成 a = b*t + k，而 t = a/b（這里的 “/” 指的是整除），k = a%b ，所以 可以得到a = b*(a/b) +k ?--> ?k=a-(a/b)*b ?--> ?a%b = a - (a/b)*b，代入?b*x1 + (a%b)*y1 = gcd。

　　那么，我們可以進(jìn)一步得到：gcd = b*x1 + (a-(a/b)*b)*y1
　　　　　　　　　　　　 　　　　 ?= b*x1 + a*y1 – (a/b)*b*y1
　　　　　　　　　　 ??　　　　　　= a*y1 + b*(x1 – a/b*y1)

? ? 　對(duì)比之前我們的狀態(tài)：求一組 x 和 y 使得：a*x + b*y = gcd ，是否發(fā)現(xiàn)了什么？

? ? 　這里：?x = y1

? ? ? ? 　　　y = x1 – a/b*y1

　　現(xiàn)在我們找到一組特殊的解 ?x₀ 和 y₀，那么，我們就可以用 x₀ 和 y₀ 表示出整個(gè)不定方程的通解：

　　　　?x = x₀ + (b/gcd)*t ?（ t 取任意整數(shù)）

? ? ? ? 　　y = y₀ – (a/gcd)*t

　　如果我們想要得到 x 大于 0 的第一個(gè)解的話，那么表達(dá)式就是：

　　　　b /= d

　　　　x = ( x₀%b + b) % b

? ? 　以上就是擴(kuò)展歐幾里德算法的全部過程，依然用遞歸寫：

1 public class ExtGcd { 2 static long x; 3 static long y; 4 5 public static long gcd(long m, long n) { 6 return n == 0 ? m : gcd(n, m % n); 7 } 8 /** 9 * 擴(kuò)展歐幾里得 10 * 調(diào)用完成后 靜態(tài)變量xy是ax+by=m的解 11 * 返回的還是最大公約數(shù) 12 */ 13 public static long ext_gcd(long a,long b){ 14 if (b==0) { // 求出了最大公約數(shù) 為a 15 x = 1; 16 y = 0; 17 return a; 18 } 19 long res = ext_gcd(b, a % b); 20 //x,y已經(jīng)被下一層遞歸更新了 21 long x1 = x;//備份x 22 x = y;//更新x 23 y = x1 - a / b * y;//更新y 24 return res; 25 } 26 public static void main(String[] args) { 27 System.out.println(ext_gcd(2, 7)); // 1 28 System.out.println(x+" "+y); // -3 1 29 } 30 }

　　最后再來看一下這個(gè)線性方程（或者叫二元一次不定方程）：ax+by = m 。有整數(shù)解時(shí)當(dāng)且僅當(dāng)m是gcd的倍數(shù)

public static long linearEquation(long a, long b, long m) throws Exception {long d = ext_gcd(a, b);//m不是gcd(a,b)的倍數(shù),這個(gè)方程無解if (m % d != 0) {throw new Exception("無解");}long n = m / d;//約一下,考慮m是d的倍數(shù)x *= n;y *= n;return d;}

　　擴(kuò)展歐幾里德算法的應(yīng)用主要有以下兩個(gè)方面：

　　　（1）求解不定方程；

　　　（2）求解模線性方程（線性同余方程）與逆元；

轉(zhuǎn)載于:https://www.cnblogs.com/xiaoyh/p/10331666.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。