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