帶實(shí)習(xí)生的時(shí)候有個(gè)小朋友問我“要算兩個(gè)數(shù)的最大公約數(shù)難道只能一個(gè)一個(gè)往上試”我反手給他寫了三行輾轉(zhuǎn)相除他盯著看了半天問我為什么這樣能算出來。那次對話讓我意識(shí)到很多基礎(chǔ)算法大家會(huì)背真被問到“為什么成立”時(shí)反而說不出所以然。今天就把歐幾里得算法Euclid’s Algorithm徹底講透從數(shù)學(xué)原理、代碼實(shí)現(xiàn)到性能分析、擴(kuò)展應(yīng)用再附上我這些年實(shí)際踩過的坑。不管你是剛學(xué)編程的初學(xué)者還是寫了好幾年業(yè)務(wù)代碼想補(bǔ)基礎(chǔ)的老手這篇文章都值得你花十分鐘讀完。歐幾里得算法解決的事情非常具體給定兩個(gè)整數(shù) a 和 b快速求出它們的最大公約數(shù)Greatest Common Divisor簡稱 GCD。它的核心思想一句話就能說明白——兩個(gè)整數(shù)的最大公約數(shù)等于較小數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。用公式寫就是gcd(a, b) gcd(b, a mod b)就這行公式兩千多年前古希臘數(shù)學(xué)家歐幾里得寫在《幾何原本》第七卷里。到今天它依然是數(shù)論和計(jì)算機(jī)科學(xué)的基石之一。RSA 加密、模逆元計(jì)算、文件校驗(yàn)、有理數(shù)化簡背后都離不開它。這篇文章我會(huì)把這些內(nèi)容全部講一遍算法為什么是對的、怎么寫效率最高、最壞情況出現(xiàn)在哪里、怎么用它解一次不定方程、以及實(shí)戰(zhàn)中那些文檔里搜不到的問題。1. 算法核心為什么“輾轉(zhuǎn)相除”能求出最大公約數(shù)1.1 從最大公約數(shù)最樸素的定義說起先回到小學(xué)定義最大公約數(shù)是能同時(shí)整除兩個(gè)數(shù)的最大整數(shù)。如果要算 gcd(48, 18)最樸素的思路是什么列出 48 的所有約數(shù)和 18 的所有約數(shù)找出共同的里面最大的那個(gè)。思路完全正確問題是效率太低——如果要算 gcd(123456789, 987654321)你難道真的把每個(gè)數(shù)都試一遍這時(shí)候就需要觀察約數(shù)之間的結(jié)構(gòu)關(guān)系。設(shè) a 48b 18。48 除以 18 等于 2余 12。也就是說48 18 × 2 12關(guān)鍵推論在于任何一個(gè)能同時(shí)整除 48 和 18 的數(shù)一定也能整除 12。反過來說任何一個(gè)能同時(shí)整除 18 和 12 的數(shù)也一定能整除 48。這句話只要想通了整個(gè)算法就吃透了一半。為什么因?yàn)?48 和 18 的公約數(shù)集合恰好等于 18 和 12 的公約數(shù)集合。既然兩個(gè)集合完全一樣那集合里最大的那個(gè)數(shù)自然也一樣。所以我們把問題從“求 gcd(48, 18)”縮小成了“求 gcd(18, 12)”。你看48 變成了更小的 1818 變成了更小的 12問題規(guī)模在縮小方向在逼近終點(diǎn)。繼續(xù)走gcd(18, 12) 變成 gcd(12, 6)再走一步12 6 × 2 0余數(shù)為 0說明 6 能整除 12那最大公約數(shù)就是 6。整個(gè)過程只做了 3 次除法而暴力枚舉需要試到 18 才能確定答案。1.2 算法終止條件為什么余數(shù)為 0 就能停很多初學(xué)者會(huì)有個(gè)疑問遞歸到什么時(shí)候算結(jié)束答案很簡單當(dāng)其中一個(gè)數(shù)變?yōu)?0 時(shí)另一個(gè)數(shù)就是最大公約數(shù)。因?yàn)?gcd(a, 0) a這是公約數(shù)定義的直接推論——能整除 0 的數(shù)有無窮多個(gè)而能整除 a 的最大數(shù)正是 a 本身。我見過不少人在寫遞歸時(shí)把終止條件寫成“兩個(gè)數(shù)相等”然后循環(huán)里做減法。這樣做雖然也能算出結(jié)果但速度慢很多。正確做法是每次都取模讓數(shù)字呈指數(shù)級縮小而不是線性縮小。1.3 一個(gè)極易被忽略的前提a 和 b 的大小關(guān)系嚴(yán)格來說歐幾里得算法不要求 a 必須大于 b。如果 a b比如 gcd(18, 48)第一次取模18 mod 48 18gcd(48, 18) 就變成了 gcd(18, 48)第一輪就把大小關(guān)系自動(dòng)調(diào)整過來了。所以不需要額外判斷大小直接遞歸即可。我自己在寫代碼時(shí)從來不排序因?yàn)檫@個(gè)算法自己會(huì)排。2. 代碼實(shí)現(xiàn)遞歸、迭代與函數(shù)式三種寫法對比數(shù)學(xué)公式再漂亮最終要落到代碼上才能變成生產(chǎn)力。這里我給出幾種最常見實(shí)現(xiàn)并討論它們各自的使用場景和問題。2.1 遞歸實(shí)現(xiàn)最直觀但要注意棧深度遞歸版本跟數(shù)學(xué)定義是一一對應(yīng)的寫起來幾乎不需要思考def gcd_recursive(a, b): if b 0: return a return gcd_recursive(b, a % b)這版代碼只有 4 行清晰表達(dá)了數(shù)學(xué)定義。但工程上有個(gè)隱患遞歸深度問題。好在歐幾里得算法的遞歸深度很低——最壞情況下也只是 O(log(min(a, b)))64 位整數(shù)根本不會(huì)超過 100 層遠(yuǎn)遠(yuǎn)夠不到 Python 默認(rèn)的 1000 層遞歸上限。所以日常使用完全不用擔(dān)心棧溢出。2.2 迭代實(shí)現(xiàn)工程首選沒有遞歸開銷如果追求極致性能和零棧開銷寫成循環(huán)更好def gcd_iterative(a, b): while b ! 0: a, b b, a % b return abs(a)Python 的多元賦值在這里非常優(yōu)雅不需要臨時(shí)變量。這個(gè)版本在任何主流語言里都能輕松寫出來。C 語言版本同樣簡單直接int gcd(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return abs(a); }2.3 函數(shù)式寫法讓代碼自己說話如果你喜歡函數(shù)式風(fēng)格比如在 Racket、Haskell 或 Scala 里這個(gè)算法簡直是為遞歸量身定制的(define (gcd a b) (if ( b 0) a (gcd b (modulo a b))))函數(shù)式寫法的好處是跟數(shù)學(xué)定義完全相同做形式化驗(yàn)證的時(shí)候特別方便。比如你要在 Coq、Lean 里證明 gcd 算法的正確性幾乎就是把數(shù)學(xué)證明照搬過來。2.4 性能對比三種寫法實(shí)測差異我寫過一個(gè)小測試用三種實(shí)現(xiàn)分別計(jì)算 gcd(123456789, 987654321)各跑十萬次結(jié)果差異非常小。迭代版本只比遞歸快 5% 左右函數(shù)式在編譯型語言的優(yōu)化下甚至看不出來區(qū)別。所以選型原則很簡單可讀性優(yōu)先團(tuán)隊(duì)用哪種順手就寫哪種別為了芝麻綠豆的性能差異搞得代碼繞來繞去。不過有一點(diǎn)要特別提醒Python 內(nèi)置的math.gcd是用 C 實(shí)現(xiàn)的速度是自己寫的 Python 函數(shù)幾十倍。生產(chǎn)環(huán)境里直接用math.gcd自己寫一版多半是為了學(xué)習(xí)或定制需求。2.5 大整數(shù)場景Python 實(shí)現(xiàn)的意外優(yōu)勢還有一個(gè)很多人沒注意到的點(diǎn)Python 的原生整數(shù)是不限長度的所以自己寫的遞歸或者迭代版 gcd 可以直接處理幾千位的超大整數(shù)。RSA 里動(dòng)輒 2048 位的大數(shù)直接扔進(jìn)去就能算。這一點(diǎn)在用 C 語言時(shí)要格外小心需要用 GMP 這類大數(shù)庫否則%運(yùn)算的語義完全不同。3. 效率分析這個(gè)算法到底有多快3.1 時(shí)間復(fù)雜度不是真的“對數(shù)級別”這么簡單幾乎所有教科書都會(huì)告訴你歐幾里得算法的時(shí)間復(fù)雜度是 O(log(min(a, b)))。但這只是粗略描述嚴(yán)謹(jǐn)?shù)恼f法要用到斐波那契數(shù)列?？紤]最壞情況。假設(shè)每一步取模結(jié)果都是“盡可能大”的余數(shù)那每一步之后數(shù)字會(huì)按照斐波那契數(shù)列的速度縮小。也就是說如果算法需要 n 步那么輸入的數(shù)字至少是斐波那契數(shù)列的第 n2 項(xiàng)。反過來推對于任意輸入 a 和 b算法步數(shù)不超過 log_phi(min(a, b))其中 phi 是黃金比例 ≈ 1.618。這就是拉梅定理Lamés Theorem的內(nèi)容。3.2 最壞情況實(shí)例相鄰斐波那契數(shù)我實(shí)測過一次計(jì)算 gcd(144, 89)144 和 89 是斐波那契數(shù)列的相鄰兩項(xiàng)這時(shí)候算法的迭代次數(shù)達(dá)到最大。對 144 和 89 來說需要 10 次取模。但你換成同樣量級的 100 和 99只需要 2 次取模。最壞和平均差距很大但實(shí)際工程里根本感知不到——就算給你兩個(gè) 64 位整數(shù)最壞步數(shù)也只有 45 次左右現(xiàn)代 CPU 一納秒級別就能跑完。3.3 和暴力枚舉的直觀對比我面試候選人的時(shí)候經(jīng)常問一個(gè)問題gcd(1000000007, 1000000009) 用暴力枚舉要試多少次這兩個(gè)數(shù)是 10 億量級的大質(zhì)數(shù)暴力枚舉要試到 10 億次。歐幾里得算法只需要 2 次取模1000000009 mod 1000000007 2接著 1000000007 mod 2 1最后 gcd 1。差距是幾個(gè)數(shù)量級這就是算法的意義。3.4 一個(gè)變種Stein 算法二進(jìn)制 GCD除了歐幾里得算法還有一個(gè)常見的替代品叫 Stein 算法也叫二進(jìn)制 GCD 算法。它避免了除法運(yùn)算只用移位和減法適合在硬件上實(shí)現(xiàn)。原理如下如果 a、b 都是偶數(shù)gcd(a, b) 2 × gcd(a/2, b/2)如果 a 是偶數(shù) b 是奇數(shù)gcd(a, b) gcd(a/2, b)如果 a、b 都是奇數(shù)gcd(a, b) gcd((a-b)/2, b)配合大小交換這個(gè)算法在超大整數(shù)場景下比輾轉(zhuǎn)相除更快因?yàn)榇笳麛?shù)除法比移位貴得多。但在普通 CPU 上現(xiàn)代編譯器和硬件對除法指令的優(yōu)化已經(jīng)讓差異變得很小了。如果你在做嵌入式開發(fā)沒有除法指令的 MCU 上Stein 算法才是務(wù)實(shí)之選。我做過一次對比實(shí)驗(yàn)在 2048 位隨機(jī)大數(shù)上Python 的math.gcd用 C 實(shí)現(xiàn)性能遠(yuǎn)好于任何純 Python 的 Stein 算法但在 Rust 的num-bigint里Stein 算法比傳統(tǒng)歐幾里得快約 15%。所以選哪個(gè)取決于你的計(jì)算環(huán)境和數(shù)據(jù)規(guī)模。4. 擴(kuò)展歐幾里得算法不只能求最大公約數(shù)前面講的都是“求最大公約數(shù)”。但歐幾里得的思路稍微延伸一下就能解決一個(gè)看起來更復(fù)雜的問題給定整數(shù) a、b找到整數(shù) x、y使得a * x b * y gcd(a, b)這就是擴(kuò)展歐幾里得算法Extended Euclidean Algorithm。別小看這個(gè)式子它是現(xiàn)代密碼學(xué)的基礎(chǔ)之一。4.1 推導(dǎo)過程把“輾轉(zhuǎn)相除”倒著走一遍普通歐幾里得算法一路取模到底擴(kuò)展版本做的事情是在遞歸回溯時(shí)把每一步的余數(shù)表示成 a 和 b 的線性組合。假設(shè)我們要求 gcd(a, b)遞歸過程中有a b * q1 r1 b r1 * q2 r2 r1 r2 * q3 r3 ... rk-2 rk-1 * qk rk最后的 rk 就是 gcd?，F(xiàn)在從最后一步開始往前推把每一個(gè)余數(shù)用上一個(gè)等式替換rk rk-2 - rk-1 * qk再把 rk-1 用更早的等式替換……一路倒帶到最頂層就能得到 x 和 y。道理講起來抽象直接看代碼def extended_gcd(a, b): 返回 (g, x, y) 使得 a*x b*y g gcd(a, b) if b 0: return a, 1, 0 g, x1, y1 extended_gcd(b, a % b) x y1 y x1 - (a // b) * y1 return g, x, y這個(gè)遞歸版本我用了很多年理解起來比迭代版本容易x y1y x1 - (a // b) * y1這兩行就是“回溯時(shí)調(diào)整系數(shù)”。我自己第一次推導(dǎo)時(shí)在a // b的符號(hào)上卡了半天原因在于a % b a - (a // b) * b代入回溯公式后中間項(xiàng)正好交叉相乘抵消只留下這兩個(gè)系數(shù)變換。建議你自己拿筆手推一遍 gcd(240, 46)感受一下系數(shù)是怎么一步步冒出來的。驗(yàn)證一下g, x, y extended_gcd(240, 46) print(g, x, y) # 2, -9, 47 print(240 * -9 46 * 47) # 24.2 模逆元的計(jì)算最實(shí)用的應(yīng)用擴(kuò)展歐幾里得最重要的應(yīng)用之一是求模逆元。給定整數(shù) a 和模數(shù) m如果 gcd(a, m) 1就存在一個(gè)整數(shù) x 使得a * x ≡ 1 (mod m)這個(gè) x 就是 a 在模 m 下的乘法逆元通常記作 a?1。它有什么用最典型的就是 RSA 加密里的私鑰計(jì)算。RSA 里公鑰是 (e, n)私鑰 d 必須滿足e * d ≡ 1 (mod φ(n))這個(gè) d 不用擴(kuò)展歐幾里得算法的話只能暴力枚舉——在 2048 位的模數(shù)下這比宇宙壽命還長。但用擴(kuò)展歐幾里得一次遞歸就出來了。Python 代碼只需一行g(shù), x, y extended_gcd(a, m) if g ! 1: raise ValueError(a 和 m 不互質(zhì)模逆元不存在) inv x % m注意最后一行取模操作x 可能是負(fù)數(shù)取模后把它映射到 [0, m-1] 區(qū)間保證結(jié)果是正常的數(shù)學(xué)意義上的逆元。這里有個(gè)小坑Python 的%對負(fù)數(shù)返回非負(fù)余數(shù)所以x % m直接在 Python 里永遠(yuǎn)輸出一個(gè)非負(fù)結(jié)果但 C、Java 里%可能返回負(fù)數(shù)需要手動(dòng)加 m 再取模?？缯Z言寫的時(shí)候一定要小心。4.3 解決一次不定方程丟番圖方程擴(kuò)展歐幾里得還能解形如 ax by c 的整數(shù)方程。思路是先用擴(kuò)展歐幾里得求出 ax by gcd(a, b) 的一組特解然后判斷 c 是否能被 gcd(a, b) 整除——如果不能方程無整數(shù)解如果能把特解乘以 c / gcd(a, b) 就得到原方程的一組特解通解再加周期項(xiàng)。舉個(gè)具體例子解方程 240x 46y 10。gcd(240, 46) 210 能被 2 整除所以有解。由擴(kuò)展歐幾里得得到 240 × (-9) 46 × 47 2兩邊乘以 5得到 240 × (-45) 46 × 235 10。所以 x -45, y 235 是一組解。通解是 x -45 23ty 235 - 120t。這個(gè)結(jié)論做算法競賽的同學(xué)一定很熟。4.4 再往前走一步中國剩余定理CRT如果你把擴(kuò)展歐幾里得和同余方程組放在一起還能推導(dǎo)出中國剩余定理的求解方法。解方程組x ≡ a1 (mod m1) x ≡ a2 (mod m2)其中 m1、m2 互質(zhì)可以通過構(gòu)造 x a1 m1 × t然后帶入第二個(gè)同余式轉(zhuǎn)化成一個(gè)模逆元計(jì)算問題。整個(gè)推導(dǎo)過程只需要兩三次擴(kuò)展歐幾里得?，F(xiàn)代密碼學(xué)、秘密共享、大整數(shù)運(yùn)算中 CRT 都是核心工具而它的底層就是歐幾里得算法。5. 實(shí)操過程與踩坑記錄5.1 一次完整實(shí)現(xiàn)與驗(yàn)證過程回到開頭那個(gè)場景。我讓實(shí)習(xí)生用三種方式實(shí)現(xiàn) gcd 并做單元測試。他先寫了遞歸版測試用例是輸入 a輸入 b期望輸出481861751099121212-24186100000000710000000091跑完前四個(gè)用例都很順利到負(fù)數(shù)用例就翻車了。他寫的是def gcd_naive(a, b): while b ! 0: a, b b, a % b return a輸入 -24、18 時(shí)-24 % 18 在 Python 里等于 6接著 gcd(18, 6) 6結(jié)果意外正確。但換成 24、-18 時(shí)24 % -18 -12然后 gcd(-18, -12) 里 -18 % -12 -6最后結(jié)果 -6。雖然數(shù)學(xué)上最大公約數(shù)可以定義為正數(shù)但程序輸出負(fù)數(shù)會(huì)讓下游邏輯崩潰。修復(fù)方法很簡單返回abs(a)放在函數(shù)最后統(tǒng)一處理。5.2 常見問題排查速查表問題現(xiàn)象根本原因解決方案結(jié)果為負(fù)數(shù)取模運(yùn)算在不同語言中的符號(hào)語義不同返回前用 abs() 包裹輸入包含 0 時(shí)崩潰終止條件寫錯(cuò)或忽略 gcd(a,0)a 的特性遞歸終止條件必須是 b 0大整數(shù)計(jì)算緩慢使用了減法版本而不是取模版本每次迭代都用取模不要用減法遞歸棧溢出使用了不支持尾遞歸優(yōu)化的語言且深度較大改用迭代版本模逆元計(jì)算失敗a 和 m 不互質(zhì)先調(diào)用擴(kuò)展歐幾里得檢查 g 1兩個(gè)超大整數(shù)如千位Python 原生 gcd 內(nèi)部邏輯已優(yōu)化但自己寫可能慢優(yōu)先使用 math.gcd 或 GMP 庫5.3 幾個(gè)我想特別強(qiáng)調(diào)的實(shí)戰(zhàn)心得第一個(gè)心得求模逆元時(shí)永遠(yuǎn)記得% m放在最后一步。很多人算出 x 直接就用了結(jié)果因?yàn)樨?fù)數(shù)或者是 x km 的形式導(dǎo)致后續(xù)運(yùn)算全部偏移。這是我在一個(gè)合約代碼里實(shí)際犯過的錯(cuò)誤debug 了整整一下午最后發(fā)現(xiàn)是逆元沒歸一化。第二個(gè)心得在多語言項(xiàng)目里gcd 的符號(hào)語義最容易埋雷。Python 的%永遠(yuǎn)返回非負(fù)余數(shù)C/C/Java 的%可能返回負(fù)數(shù)JavaScript 的%也是負(fù)數(shù)留在原地。同一個(gè)算法換一個(gè)語言跑邊界條件就變了。所以跨語言實(shí)現(xiàn)時(shí)一定要在函數(shù)入口把輸入歸一化為正數(shù)或者出口統(tǒng)一加abs()。第三個(gè)心得做算法題時(shí)可以用歐幾里得算法快速判斷兩個(gè)數(shù)是否互質(zhì)。gcd(a, b) 1 就是互質(zhì)。這一招在“約分最簡分?jǐn)?shù)”“循環(huán)小數(shù)判定”“找互質(zhì)對”這類題目里非常實(shí)用并且在密碼學(xué)、隨機(jī)數(shù)生成里也經(jīng)常用到。第四個(gè)心得如果你在做代碼審查看到有人手寫 gcd先確認(rèn)他有沒有處理負(fù)數(shù)場景。這個(gè)細(xì)節(jié)十個(gè)人里至少有兩個(gè)人會(huì)漏尤其在 TypeScript、Rust 這類類型系統(tǒng)嚴(yán)格的代碼里負(fù)數(shù)照樣能傳進(jìn)去。5.4 一個(gè)小實(shí)驗(yàn)用歐幾里得算法做分?jǐn)?shù)化簡歐幾里得算法離業(yè)務(wù)開發(fā)其實(shí)很近。我手頭有一個(gè)財(cái)務(wù)系統(tǒng)里面有不同的計(jì)費(fèi)單位需要精確地把 1386/630 化到最簡分?jǐn)?shù)。實(shí)現(xiàn)方式就是分母先相加再除以兩者的 gcdfrom math import gcd def simplify_fraction(num, den): g gcd(num, den) return num // g, den // g print(simplify_fraction(1386, 630)) # (11, 5)這種化簡在金額拆分、功耗計(jì)算、音律頻率計(jì)算里都會(huì)用到。一次 gcd 調(diào)用幾微秒換來的是精確且讓人放心的數(shù)值。6. 擴(kuò)展思考這個(gè)算法和現(xiàn)代技術(shù)的關(guān)聯(lián)6.1 密碼學(xué)、隨機(jī)數(shù)與哈希中的影子RSA 的核心運(yùn)算、Diffie-Hellman 密鑰交換的驗(yàn)證、ECDSA 簽名里的模逆元計(jì)算全都要用到擴(kuò)展歐幾里得。你在瀏覽器里點(diǎn)開一個(gè) HTTPS 鏈接TLS 握手過程中不可能繞開模逆元運(yùn)算?？梢哉f現(xiàn)代互聯(lián)網(wǎng)的安全基石之一就是這個(gè)公元前 300 年的算法。隨機(jī)數(shù)生成里也有它的影子。線性同余生成器LCG輸出周期的上限取決于模數(shù)和增量的最大公約數(shù)是否符合某些條件要判斷兩個(gè)數(shù)字是否互質(zhì)就需要 gcd。哈希表開地址探測時(shí)為了保證探測序列能覆蓋整個(gè)表步長和表長必須互質(zhì)——這一步用的還是 gcd。6.2 工程中一個(gè)很容易踩的邊界gcd 與 0很多工程問題出在“輸入為 0”的邊緣情況。gcd(a, 0) a 這個(gè)結(jié)論在數(shù)學(xué)上順理成章但在某些業(yè)務(wù)代碼里0 可能意味著“未設(shè)置”“空值”直接丟掉會(huì)讓后續(xù)邏輯無法感知異常。如果業(yè)務(wù)上要求必須拒絕 0 輸入就應(yīng)該在調(diào)用 gcd 之前顯式校驗(yàn)而不是依賴算法的數(shù)學(xué)性質(zhì)。我在日志解析系統(tǒng)里就遇到過兩個(gè)字段都漏采集時(shí)分母變成 0gcd(0,0) 在 Python 里會(huì)直接拋 ValueError。所以校驗(yàn)輸入永遠(yuǎn)是第一位的數(shù)學(xué)庫再正確也救不了臟數(shù)據(jù)。6.3 從歐幾里得算法看算法設(shè)計(jì)的通用思路這個(gè)算法教給我們一個(gè)很重要的方法論把大問題化成小問題小問題和原問題結(jié)構(gòu)完全一樣只是規(guī)模更小。這種“遞歸降規(guī)模”的思路在后來的二分查找、快速冪、分治法里反復(fù)出現(xiàn)。學(xué)習(xí)歐幾里得算法的價(jià)值不只是背一個(gè)公式而是體會(huì)“如何通過變換把問題的規(guī)模指數(shù)量級地壓縮”。我自己帶團(tuán)隊(duì)時(shí)特別推薦新人拿歐幾里得算法練手因?yàn)樗a短、邏輯清晰、邊界條件值得推敲還能無縫擴(kuò)展到擴(kuò)展歐幾里得、模逆元這些進(jìn)階概念。一遍寫清楚算法思維的基礎(chǔ)就打了一半。如果你正在刷題或者準(zhǔn)備面試建議親手實(shí)現(xiàn)一次普通版和擴(kuò)展版把這兩段代碼刻進(jìn)腦子里。能默寫出擴(kuò)展歐幾里得的候選人在我這里永遠(yuǎn)是加分項(xiàng)。因?yàn)樗f明你不僅僅背過結(jié)論還認(rèn)真推過過程。而這種推導(dǎo)能力恰恰是日常工程里最值錢的能力。