難度較高，閱讀時間大概 28 分鐘

這是數(shù)論的第二篇，在《素?cái)?shù)篩法》中，我們重溫了素?cái)?shù)這個數(shù)學(xué)定義，并且給出了區(qū)別于教科書上更高效的 Eratosthenes 篩法和歐拉線性篩。這篇文會從 GCD 問題出發(fā)，一起來探究一下擴(kuò)展歐幾里得算法。

看了標(biāo)題，也許你有疑問，什么是歐幾里得算法？歐幾里得算法是為了解決 GCD 問題，這里的 GCD 是指 Greatest Common Divisor 即?最大公約數(shù)，而不是 iOS 中的 Grand Central Dispatch ? 。所以這篇分享是關(guān)于算法的。

歐幾里得算法(GCD)

求 GCD 在數(shù)論中公認(rèn)的最常用算法即為歐幾里得算法，也就是我們在高中時學(xué)到的輾轉(zhuǎn)相除法。

歐幾里得算法的基本原理用一句話就可以說清楚：兩個整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)的差的最大公約數(shù)，即 gcd(a, b) = gcd(b, a mod b)。

為什么可以這么求呢，這里可以簡單證明一下：

假設(shè) a, b (a > b) 兩個數(shù)的一個公約數(shù)是 t ，則有

因?yàn)?a > b ，設(shè) a = k × b + r ，即 r = a mod b ，將 a、b 代入展開可得：

由于 (n - k × m) × t 一定是整數(shù)，所以 a、b 的公約數(shù) t 也是 r 的約數(shù)。所以如果我們遞歸的求解 a mod b 也就是 a % b ，就可以得到 a、b 的最大公約數(shù) GCD 了。什么時候遞歸結(jié)束呢？當(dāng) a % b == 0 的時候，因?yàn)樵谶@個過程中，如果 a mod b 無法求得正整數(shù) r 時，則無法繼續(xù)按照上述規(guī)律繼續(xù)拆分。

# pythondef gcd(a, b): return a if b == 0 else gcd(b, a % b)// Cint gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b);}

這里另外提一句，a、b 兩數(shù)的最大公倍數(shù) LCM(a, b) = a * b / GCD(a, b) 。這里就不證明了，有興趣的自己谷歌。

一道頭條的筆試題

上個月在脈脈上看到一道頭條校招的筆試題，看評論說是“地獄難度”的，我們通過這道題來延伸說一下。先來看下這題的題面：

---

有一臺用電容組成的計(jì)算器，其中每個電容組件都有一個最大容量值(正整數(shù))。對于單個電容，有如下操作指令：

指令1：放電操作-把該電容當(dāng)前電量值清零；

指令2：充電操作-把該電容當(dāng)前電量補(bǔ)充到最大容量值；

指令3：轉(zhuǎn)移操作-從電容 A 中盡可能多的將電量轉(zhuǎn)移到電容 B ，轉(zhuǎn)移不會有電量損失，如果能夠充滿 B 的最大容量，那剩余的電量仍然會留在 A 中。

現(xiàn)在已知有兩個電容，其最大容量分別為 a 和 b，其初始狀態(tài)都是電量值為 0，希望通過一些列的操作可以使其中某個電容(無所謂哪一個)中的電量值等于 c (c也是正整數(shù))，這一些列操作所用的最少指令條數(shù)記為 M，如果無論如何操作，都不可能完成，則定義此時 M = 0。

顯然對于每一組確定的 a,b,c，一定會有一個 M 與之對應(yīng)。

這里需要輸入的是 a、b、c ，給出兩個樣例，例如 a = 3, b = 4, c = 2 ，則最少需要 4 個指令完成。

---

解釋：設(shè)最大容量為 3 的是 A 號電容，另一個是 B 號電容，對應(yīng)的操作是 (充電 A)=> (轉(zhuǎn)移 A -> B) => (充電 A)=> (轉(zhuǎn)移 A -> B) ，這樣 A 就是目標(biāo)的 2 電量。

第二個樣例 a = 2, b = 3, c = 4，由于 a 和 b 都無法到目標(biāo)電量 4，所以輸出 0 代表無解。

這道題我們拿到以后，第一反應(yīng)就是模擬三個指令，然后使用 BFS 廣度優(yōu)先搜索來搜出答案，只要任意情況到達(dá)目標(biāo)的 c 值就停下來。但是題目中給出了數(shù)據(jù)量 0 < a, b, c < 10^9 ，這個數(shù)據(jù)量約束了我們無法使用暴力搜索來求解。

簡要分析

首先從筆試的角度來分析，由于筆試時會有數(shù)據(jù)范圍的測試，這道題給出的數(shù)據(jù)范圍大概是這樣：

0?c?10^0?c?10^0?c?10^

所以如果沒有任何的思路和數(shù)論基礎(chǔ)，我建議使用 BFS 直接寫一版暴力，最少可以通過 > 50% 的數(shù)據(jù)，從而拿到一定的分?jǐn)?shù)。(其實(shí)這就是 OI 得分賽制，沒有思路先暴力搶分)。

下面我們來分情況討論這個問題：

情況一

樣例已經(jīng)給出了一種邊界情況，即當(dāng) c > max(a, b) ，這種情況是無法使得 A 和 B 的電量達(dá)到 c 的。直接輸出 0。

情況二

還有一種我們可以直接想到的情況，當(dāng) a = c 或者 b = c 的時候，只進(jìn)行一次充電操作就可以完成，直接輸出 1。

情況三

接下來我們考慮一般情況，即需要滿足以下前提條件：

我們將這個問題換一個思路轉(zhuǎn)化一下假設(shè)給出的 a 、b、 c 一定有解，那么我們來設(shè)置對 A 做了 x 次的充(放)電，對 B 做了 y 次的充(放)電，并且做了 k 次的操作三。如果將 A、B 當(dāng)做一個大電容來看這個電容只有充放電 a 單位、充放電 b 單位這 4 種操作。那么我們就可以列出一個關(guān)系式：

由于 a、b 為非負(fù)整數(shù)，又因?yàn)榍疤釛l件 c < max(a, b) ，則 x 和 y 符號相反。

暫且，我們先不管做了幾次操作三，先只考慮充放電問題，那其實(shí)就是已知 a、b、c，我們在給定范圍內(nèi)求解 x 和 y 的解就可以了。那么這個問題我們要如何求解呢？這就是擴(kuò)展歐幾里得算法所要解決的問題。

擴(kuò)展歐幾里得算法(Extended Euclidean)

帶 * 的章節(jié)略有難度。如果是從解決問題的工程角度出發(fā)，可以跳過證明直接記結(jié)論。

在推導(dǎo)上述問題的求解算法之前，我們需要先了解以下幾個概念知識。

丟番圖方程(Diophantine Equation)

丟番圖方程指的是：未知數(shù)個數(shù)多于方程個數(shù)，且未知數(shù)只能是整數(shù)的整數(shù)系數(shù)方程或方程組。例如以下式中，a、b、c 都為整數(shù):

關(guān)于代數(shù)學(xué)鼻祖丟番圖(Diophantus)除了有《算數(shù)》這本開山巨作之外，還有一個好玩的數(shù)學(xué)題目墓志銘，有興趣可以自己了解。

裴蜀定理(Bézout's identity)

在數(shù)論中，裴蜀定理是一個關(guān)于最大公約數(shù)的定理。這個定理說明了對于任意整數(shù) a、b 和他們的最大公約數(shù) d，關(guān)于未知數(shù) x 和 y 的線性丟番圖方程：

有解，當(dāng)且僅當(dāng) m 是 d 的倍數(shù)時。這個等式也被稱為裴蜀等式。

裴蜀等式有解時必然有無窮多個整數(shù)解，每組解 x 、y 都稱之為裴蜀數(shù)，可用輾轉(zhuǎn)相除法求得。

輾轉(zhuǎn)相除法實(shí)現(xiàn)擴(kuò)展歐幾里得算法

既然說可以用輾轉(zhuǎn)相除法來解決這個問題，那么我們先來說明一下如何通過輾轉(zhuǎn)相除法來求二元一次線性丟番圖方程。

輾轉(zhuǎn)相除法過程

以 23x + 17y = 1 為例，我們來求 GCD(23, 17)：

改寫成余數(shù)形式

將等式右邊的第一項(xiàng)移項(xiàng)：

反向帶入原式

帶下劃線的 6 和 5 會使用 (1) 和 (2) 兩個式子反向帶入，形同換元：

所以反解得，x = 3, y = -4 是上述二元一次線性丟番圖方程的一組解。

* 擴(kuò)展歐幾里得算法證明

來觀察一下輾轉(zhuǎn)相除法的最后兩個式子，終止條件是：

當(dāng)且僅當(dāng)?shù)诙€式子為 0 的時候停止這個遞歸運(yùn)算。如何延伸到一般情況呢？我們將待求變量設(shè)為字母來嘗試一下。假設(shè)此時，我們要求 an 和 bn 為系數(shù)的二元一次線性丟番圖方程的系數(shù)，即待求方程：

根據(jù)上述的改寫余數(shù)形式，我們可以列出式一(| 是整除的意思)：

假設(shè)未到達(dá)最終的終止條件，則有：

第二個式子中我們可以發(fā)現(xiàn)：

同理，第 n 個式子中有：

根據(jù)輾轉(zhuǎn)相除的規(guī)則，我們知道第 0 項(xiàng)中 b = 0、 a = 1 ，而我們要求的是第 n 項(xiàng)中的 a 和 b，所以可以通過 a 和 b 的遞推公式逐一推導(dǎo)而來。

如此我們證明了 an 和 bn 的遞推關(guān)系，下面我們來證明 xn 的遞推關(guān)系。

由上文證得了：

我們將其帶入到第一個式子中：

所以可以求得：

由于輾轉(zhuǎn)相除的推論我們可得：

所以：

即：

代碼實(shí)現(xiàn)擴(kuò)展歐幾里得算法

為了實(shí)現(xiàn)上述的反向帶入原式的過程，我們通過遞歸遞歸到最深的一層，將每一層的解帶入即可完成最終的求解：

# pythondef ex_gcd(a, b): if b == 0: return 1, 0, a else: x, y, r = ex_gcd(b, a % b) x, y = y, (x - (a // b) * y) return x, y, r// c++int ex_gcd(int a, int b, int &x, int &y) { if(b == 0) { x = 1; y = 0; return a; } int r = ex_gcd(b, a % b, x, y); int t = y; y = x - (a / b) * y; x = t; return r;}

但是我們注意到，由于裴蜀定理，我們求解的丟番圖方程中，等號右邊的常數(shù)必須是 k * gcd(a, b)。所以我們的求解其實(shí)是：

所以通過擴(kuò)展 GCD 算法求得的 x0 和 y0 這組解，并不是我們要求的最終解。同樣的，我們對其擴(kuò)大 k 倍就是我們想要對結(jié)果：

小結(jié)

有了這些知識，你對那道“地獄難度”的頭條面試題有沒有更多的想法呢？這里有一道 [LeetCode-365] 水壺問題 你可以嘗試一下，做完之后想必會對擴(kuò)展 GCD 算法有更深的理解。

至于頭條面試題，我將在下一篇文繼續(xù)講述并代碼實(shí)現(xiàn)此題的解法。

總結(jié)

以上是生活随笔為你收集整理的如何利用扩展欧几里得算法求解不定方程_客户端不用的算法系列：从头条笔试题认识扩展欧几里得算法...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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