與最小公倍數(shù)：更相減損、歐幾里得與Stein算法全解析)
看到這個標(biāo)題就很有共鳴最大公約數(shù)和最小公倍數(shù)算是算法入門里最經(jīng)典的一對“老朋友”了。不管是剛學(xué)編程準(zhǔn)備信奧還是刷LeetCode熱身幾乎所有人都會先撞到這幾行代碼。網(wǎng)上講這個的文章很多但大多數(shù)要么只給一個模板要么直接把證明甩你臉上看完能記住的沒幾個。這篇我換個思路把最大公約數(shù)的三種常見算法和最小公倍數(shù)的兩種求法放在一起拆開揉碎講清楚每個算法都交代清楚“為什么能這么算”“邊界在哪”“坑在哪”最后再補(bǔ)上實際工程和競賽里怎么選型的經(jīng)驗。想徹底搞懂這塊內(nèi)容的同學(xué)這篇可以直接收藏。1. 先搞清楚一件事最大公約數(shù)和最小公倍數(shù)的關(guān)系到底是什么很多人把這兩個概念分開記但實際上它們是一對“孿生兄弟”。對于兩個正整數(shù)a和b假設(shè)它們的最大公約數(shù)Greatest Common Divisor簡稱GCD是d最小公倍數(shù)Least Common Multiple簡稱LCM是m那么存在一個非常漂亮的關(guān)系式a × b d × m也就是說兩個數(shù)的乘積等于它們的最大公約數(shù)和最小公倍數(shù)的乘積。這個式子不是湊巧而是有嚴(yán)格數(shù)學(xué)推導(dǎo)的。簡單理解把a(bǔ)和b各自分解成質(zhì)因數(shù)的乘積gcd取的是每個質(zhì)因數(shù)的“較小指數(shù)”lcm取的是每個質(zhì)因數(shù)的“較大指數(shù)”兩者指數(shù)相加正好等于原始的指數(shù)和所以乘起來自然相等。這個關(guān)系式的價值在于求最小公倍數(shù)完全可以借助最大公約數(shù)來實現(xiàn)而最大公約數(shù)的算法在歷史上有過非常多的研究效率高而且穩(wěn)定。所以大部分時候只要會算gcdlcm就等于a / gcd(a, b) * b注意這個計算順序先除后乘可以防止溢出后面會詳細(xì)說。但這不意味著lcm就沒有自己的獨立算法了——直接分解質(zhì)因數(shù)也能求而且某些場景下反而更直觀。接下來我先把最大公約數(shù)的三種經(jīng)典算法講透再說最小公倍數(shù)的兩種求法這樣整個知識體系就閉環(huán)了。2. 最大公約數(shù)算法一更相減損術(shù)——最古老也最直觀的“減法思維”更相減損術(shù)是中國古代數(shù)學(xué)著作《九章算術(shù)》中記載的方法比歐幾里得算法還要早。它的核心思想特別樸素兩個數(shù)的最大公約數(shù)等于“較大的數(shù)減去較小的數(shù)”之后得到的差與“較小的數(shù)”之間的最大公約數(shù)。用數(shù)學(xué)語言表達(dá)就是當(dāng)a b時gcd(a, b) gcd(a - b, b)。這個式子成立的理由也不難理解任何能同時整除a和b的整數(shù)一定能整除它們的差a - b反過來任何能同時整除b和a - b的整數(shù)也一定能整除a因為a (a - b) b。所以公約數(shù)的集合完全一樣最大公約數(shù)自然也一樣。基于這個原理算法流程就是不斷用大數(shù)減小數(shù)直到兩個數(shù)相等這個相等的數(shù)就是最大公約數(shù)。用C實現(xiàn)如下int gcdBySubtraction(int a, int b) { while (a ! b) { if (a b) a - b; else b - a; } return a; }這個算法有個顯而易見的缺點如果兩個數(shù)差距懸殊比如a10000b1那就得循環(huán)減9999次性能極差。但它奠定了“通過不斷縮小問題規(guī)模來解決原問題”的遞歸思想這是后面所有算法的基礎(chǔ)。我在實際講解這個算法的時候喜歡用一個“切繩子”的類比假設(shè)有兩根長度分別為a和b的繩子要找能同時把兩根繩子都切成整數(shù)段的最大長度。更相減損術(shù)的過程就是不停地拿長繩子減短繩子把長繩子替換成剩余的部分直到兩根繩子一樣長。這個“一樣長”的長度就是最大公約數(shù)。說個實操心得更相減損術(shù)雖然效率一般但它在理解“公約數(shù)”本質(zhì)這件事上無可替代。如果你教新手先讓他寫這個再讓他寫歐幾里得算法他對取模運算的理解會深很多。這比直接甩給他一個gcd模板要有效得多。3. 最大公約數(shù)算法二歐幾里得算法輾轉(zhuǎn)相除法——競賽和工程中的絕對主力歐幾里得算法也叫輾轉(zhuǎn)相除法是現(xiàn)在應(yīng)用最廣泛的求最大公約數(shù)算法。它的核心原理和更相減損術(shù)類似但用取模運算代替減法直接實現(xiàn)“大數(shù)換成余數(shù)”gcd(a, b) gcd(b, a mod b)其中a b為什么這樣可以因為取模的本質(zhì)就是連續(xù)減法——a mod b其實就是a不斷減去b直到不夠再減為止。所以歐幾里得算法可以理解為更相減損術(shù)的“批量加速版”一次取模運算相當(dāng)于做了很多次減法。標(biāo)準(zhǔn)遞歸實現(xiàn)int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }迭代實現(xiàn)實際工程中推薦避免遞歸棧開銷int gcdIterative(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return a; }關(guān)于時間復(fù)雜度歐幾里得算法的時間復(fù)雜度是O(log min(a, b))這里log的底數(shù)大約是黃金比例φ ≈ 1.618。也就是說每次取模問題規(guī)模至少縮小一個常數(shù)倍循環(huán)次數(shù)非常少。最壞情況出現(xiàn)在兩個數(shù)是相鄰斐波那契數(shù)時比如gcd(144, 89)循環(huán)次數(shù)達(dá)到最大但那也只是十幾次而已。我在LeetCode刷題時實測過就算a和b都接近int上限約21億循環(huán)次數(shù)也基本不超過45次效率極其穩(wěn)定。這也是為什么所有語言的標(biāo)準(zhǔn)庫幾乎都內(nèi)置了gcd實現(xiàn)C17的std::gcdPython的math.gcd底層基本都用的這個算法。避坑提示遞歸寫法雖然簡潔但面試寫代碼時最好改成迭代。很多遞歸寫法在極端情況下棧深度其實還好因為深度只要幾十層但有些公司的在線評測系統(tǒng)?？臻g設(shè)置得很小萬一遇到類似情況就會無謂地棧溢出。迭代版本的性能更優(yōu)也更能體現(xiàn)你對底層原理的理解。4. 最大公約數(shù)算法三Stein算法二進(jìn)制GCD算法——大整數(shù)場景下的“特種兵”Stein算法是歐幾里得算法的強(qiáng)力補(bǔ)充它拋棄了取模運算只用減法和位運算右移、左移因此在處理超大整數(shù)時優(yōu)勢明顯。為什么拋棄取模呢因為超大整數(shù)比如幾百位的十進(jìn)制數(shù)的除法本身很費時CPU的除法指令周期遠(yuǎn)高于加減法和移位而在高精度計算中“除以2”可以用右移一位完成代價極低。Stein算法的核心規(guī)則基于以下四個觀察如果a和b都是偶數(shù)則gcd(a, b) 2 × gcd(a / 2, b / 2)。如果a是偶數(shù)、b是奇數(shù)則gcd(a, b) gcd(a / 2, b)。如果a是奇數(shù)、b是偶數(shù)則gcd(a, b) gcd(a, b / 2)。如果a和b都是奇數(shù)則gcd(a, b) gcd((a - b) / 2, b)利用更相減損術(shù)的原理。遞歸終止條件是a b此時gcd就是a也是b。C實現(xiàn)int gcdStein(int a, int b) { if (a 0) return b; if (b 0) return a; int shift 0; // 提取公共的因子2 while (((a | b) 1) 0) { a 1; b 1; shift; } // 確保a是奇數(shù) while ((a 1) 0) a 1; while (b ! 0) { while ((b 1) 0) b 1; if (a b) swap(a, b); b - a; } return a shift; }這段代碼看起來比歐幾里得算法復(fù)雜但核心思想就是“不斷消去因子2把兩個奇數(shù)的情況轉(zhuǎn)換成減法再除以2”。每次循環(huán)至少把一個數(shù)縮半整體時間復(fù)雜度仍然是O(log max(a, b))級別。適用場景說明普通int范圍內(nèi)的gcdStein算法相比歐幾里得算法并沒有明顯優(yōu)勢有時甚至稍慢因為邏輯分支更多。但在以下場景中Stein算法才是真正的王者高精度大整數(shù)計算大數(shù)取模一次的成本極其高昂而“除以2”只需要在高精度數(shù)組的首位處理一下成本低得驚人。嵌入式等對除法指令敏感的環(huán)境某些低端MCU沒有硬件除法指令取模運算通過軟件模擬會非常慢Stein算法全程只用減法和移位優(yōu)勢巨大。密碼學(xué)中的大數(shù)運算RSA等算法需要大量gcd計算其中操作數(shù)往往有幾百上千比特。從工程實踐角度看如果你只需要在普通程序里求gcd直接用歐幾里得算法沒錯但如果你在做大數(shù)運算庫或者對性能敏感的系統(tǒng)級開發(fā)Stein算法是你必須掌握的備選方案。5. 最小公倍數(shù)求法一利用gcd公式法——最通用、最推薦的方案前面提到過關(guān)鍵公式lcm(a, b) a / gcd(a, b) * b。這個式子用起來很簡單但有一個非常容易踩的坑先乘a × b再除以gcd在大數(shù)場景下會溢出。舉個例子a2^31 - 1int最大值b2^31 - 2兩者乘積大約是4.6×10^18遠(yuǎn)超int的表示范圍約2.1×10^9直接乘必然溢出。所以標(biāo)準(zhǔn)寫法一定是先除后乘int lcm(int a, int b) { return a / gcd(a, b) * b; }這樣做的數(shù)學(xué)依據(jù)a / gcd(a, b)和b互為“互質(zhì)部分”的關(guān)系兩者相乘不會超出a和b乘積的理論值但在很多情況下不會溢出。什么情況下還是會溢出呢答案是當(dāng)a和b本身就是接近極限的大整數(shù)時它們的lcm可能超出int范圍以int類型存儲無論如何都會溢出。這時就需要升級為long long或大整數(shù)類型而不能只靠調(diào)整運算順序來規(guī)避。C標(biāo)準(zhǔn)庫風(fēng)格的完整實現(xiàn)#include numeric #include algorithm long long lcm_ll(long long a, long long b) { return a / std::gcd(a, b) * b; }實操心得在競賽中處理多組數(shù)據(jù)的LCM時我習(xí)慣將a和b統(tǒng)一提升為long long再做運算并且全程使用long long保存中間結(jié)果。很多同學(xué)一開始用int存gcd的結(jié)果然后轉(zhuǎn)成long long乘結(jié)果還是溢出——因為溢出發(fā)生在int乘法階段已經(jīng)來不及了。正確做法是從頭到尾都用更大的類型。另外這個公式還有一個漂亮的性質(zhì)求多個數(shù)的lcm可以兩兩迭代計算。比如求lcm(a, b, c)可以先算lcm_ab lcm(a, b)再算lcm(lcm_ab, c)。但要注意計算過程中數(shù)值可能增長得很快所以務(wù)必使用更大范圍的數(shù)據(jù)類型每算一步都盡量先除后乘。6. 最小公倍數(shù)求法二分解質(zhì)因數(shù)法——直觀但代價更高的路徑第二種求lcm的辦法是從定義出發(fā)先把每個數(shù)分解成質(zhì)因數(shù)的冪次積然后對每個質(zhì)因數(shù)取“所有數(shù)中出現(xiàn)的最大指數(shù)”再乘起來。舉個例子求lcm(12, 18)12 22 × 3118 21 × 32對質(zhì)因數(shù)2取最大指數(shù)2對質(zhì)因數(shù)3取最大指數(shù)2所以 lcm 22 × 32 36。這種方法的直觀性極強(qiáng)特別適合用來向初學(xué)者解釋“最小公倍數(shù)到底最小在哪”每個質(zhì)因數(shù)的指數(shù)都不能小于任何一個數(shù)中該質(zhì)因數(shù)的指數(shù)否則無法整除對應(yīng)數(shù)而“最小”意味著恰好取到這些最大指數(shù)一個不多一個不少。算法實現(xiàn)上需要先準(zhǔn)備素數(shù)表可以用埃氏篩或歐拉篩然后對每個數(shù)做質(zhì)因數(shù)分解記錄每個質(zhì)因數(shù)的最大出現(xiàn)次數(shù)#include vector #include map std::vectorint sieve(int n) { std::vectorbool is_prime(n 1, true); std::vectorint primes; is_prime[0] is_prime[1] false; for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); for (int j i * i; j n; j i) { is_prime[j] false; } } } return primes; } long long lcmByFactorization(int a, int b) { std::mapint, int max_exp; // 對a分解質(zhì)因數(shù) int x a; for (int p 2; p * p x; p) { int cnt 0; while (x % p 0) { x / p; cnt; } if (cnt 0) max_exp[p] cnt; } if (x 1) max_exp[x] 1; // 對b分解質(zhì)因數(shù)并更新最大指數(shù) int y b; for (int p 2; p * p y; p) { int cnt 0; while (y % p 0) { y / p; cnt; } if (cnt max_exp[p]) max_exp[p] cnt; } if (y 1) max_exp[y] std::max(max_exp[y], 1); long long result 1; for (auto [p, e] : max_exp) { while (e--) result * p; } return result; }這種實現(xiàn)明顯比gcd公式法復(fù)雜時間復(fù)雜度也高不少——單次分解質(zhì)因數(shù)最壞情況是O(√n)再加上篩法建表的開銷在大數(shù)據(jù)量下性能遠(yuǎn)不如歐幾里得算法。但它的優(yōu)勢在于可解釋性和可擴(kuò)展性當(dāng)你需要一次性求多個數(shù)的最小公倍數(shù)并且要輸出分解過程比如數(shù)學(xué)題解題過程、教學(xué)演示這個方法無可替代。另外如果你已經(jīng)維護(hù)了一套質(zhì)因數(shù)分解系統(tǒng)順帶求lcm就是“免費”的不用額外維護(hù)新的邏輯。7. 三種GCD算法與兩種LCM求法的全面對比與選型建議我把上面幾種算法放在一起做一次橫向?qū)Ρ冗@樣選型的時候一眼就能看清楚算法核心運算時間復(fù)雜度代碼復(fù)雜度最佳適用場景更相減損術(shù)減法最壞O(max(a,b))極簡教學(xué)演示、理解公約數(shù)概念歐幾里得算法取模O(log min(a,b))簡潔通用場景、競賽刷題、標(biāo)準(zhǔn)庫實現(xiàn)Stein算法減法移位O(log max(a,b))中等超大整數(shù)、無除法硬件環(huán)境分解質(zhì)因數(shù)法求LCM質(zhì)因數(shù)分解O(√n)較復(fù)雜數(shù)學(xué)解題演示、多數(shù)組件化求LCMgcd公式法求LCM除法乘法O(log min(a,b))極簡幾乎一切工程場景首選方案選型建議默認(rèn)情況下的最優(yōu)解非常明確——最大公約數(shù)用歐幾里得算法最小公倍數(shù)用“先除后乘”的gcd公式法。這組合在時間效率、代碼可維護(hù)性、防溢出安全性上都做到最優(yōu)。但在以下場景需要重新考慮教學(xué)場景優(yōu)先用更相減損術(shù)分解質(zhì)因數(shù)法。雖然性能一般但學(xué)生能直觀看到“公約數(shù)”是如何從“不斷相減”中浮現(xiàn)的比直接給代碼要有說服力得多。大整數(shù)運算場景改用Stein算法。尤其在做高精度庫如大數(shù)RSA、密碼學(xué)算法時取模是性能殺手減法和移位才有優(yōu)勢。如果你計算的是浮點數(shù)或需要處理不一定為整數(shù)的情況gcd和lcm都只適用于整數(shù)這些算法全部作廢。請先回到問題定義確認(rèn)數(shù)據(jù)是整數(shù)再做方案選型。對于剛?cè)腴T的朋友我建議先把歐幾里得算法背得滾瓜爛熟然后自己手寫一遍迭代版和遞歸版再分別測試幾組大數(shù)對比運行時間。等你對取模的循環(huán)過程有了手感再去看Stein算法和更相減損術(shù)會發(fā)現(xiàn)它們之間的演進(jìn)關(guān)系非常自然。8. 常見問題與排查技巧實錄這塊整理我在教學(xué)和刷題過程中經(jīng)常遇到的典型問題每個都是真實踩過的坑問題1遞歸版gcd在數(shù)據(jù)很大時會棧溢出嗎不會。歐幾里得算法遞歸深度不超過O(log min(a, b))即使a、b均為max long long深度也只有幾十層離棧溢出很遠(yuǎn)。但如果你的遞歸函數(shù)寫得不小心比如每次遞歸前就復(fù)制了巨大的對象比如大整數(shù)的vector數(shù)組那棧和堆都有風(fēng)險。所以競賽中我一般直接寫迭代版不給自己留隱患。問題2用lcm(a,b) a * b / gcd(a,b)到底行不行數(shù)學(xué)上完全正確但工程上不推薦。因為a * b在int范圍內(nèi)極容易溢出而a / gcd(a, b) * b就能在很大范圍內(nèi)安全計算。我見過太多人因為這種寫法在LeetCode第1201題這類題目上交了錯誤答案調(diào)試半天才發(fā)現(xiàn)是溢出。養(yǎng)成先除后乘的習(xí)慣以后這類問題可以幾乎絕跡。問題3求0和某個數(shù)的gcd、lcm會發(fā)生什么gcd(0, n) n這是數(shù)學(xué)上的約定但lcm(0, n)嚴(yán)格來說是未定義的因為0沒有“倍數(shù)”概念。實際工程中如果你用a / gcd * b去算gcd為0時直接觸發(fā)除零錯誤所以要么提前處理a或b為0的情況要么約定輸入為正整數(shù)。在刷題時也要先看題目約束條件大多數(shù)題目明確說“a和b均為正整數(shù)”這時候就不用擔(dān)心這個問題。問題4更相減損術(shù)碰上懸殊數(shù)字算得很慢怎么區(qū)分“教學(xué)價值高”和“實際不可用”我的經(jīng)驗是更相減損術(shù)適合在小范圍數(shù)據(jù)或課堂教學(xué)中使用一旦數(shù)據(jù)超過一萬量級性能問題就會非常突出。如果在競賽題里看到需要計算gcd且數(shù)據(jù)范圍很大直接放棄更相減損術(shù)上歐幾里得不要有心理負(fù)擔(dān)。理解它的原理就夠了不意味著必須在所有場景用它。問題5多個數(shù)的gcd和lcm有沒有什么優(yōu)化技巧多個數(shù)的gcd就是從頭到尾兩兩迭代gcd順序不影響結(jié)果lcm同樣兩兩迭代但注意結(jié)果是“越迭代越大”所以如果題目的最終要求是取模輸出最好在迭代過程中每步都取模防止中間結(jié)果爆炸。比如求n個數(shù)lcm對某個mod取模可以每次lcm算完直接 % mod但如果后續(xù)還要用這個lcm去求別的數(shù)就不能只保存取模后的值而應(yīng)該用適當(dāng)?shù)拇髷?shù)類型保存完整結(jié)果。這個細(xì)節(jié)在題目“求n個數(shù)的lcm對mod取模”中經(jīng)常出現(xiàn)需要根據(jù)題目要求靈活處理。問題6為什么標(biāo)準(zhǔn)庫的std::gcd有時比手寫慢標(biāo)準(zhǔn)庫實現(xiàn)通常會處理更多邊界情況包括負(fù)數(shù)、類型轉(zhuǎn)換等并且開啟了異常檢查所以可能比手寫簡單版本稍慢。但這差別微乎其微工程中完全沒有必要因此放棄標(biāo)準(zhǔn)庫。不過在處理超高頻率調(diào)用gcd的算法題目時比如某些數(shù)論題中循環(huán)幾十萬次手寫一個不帶邊檢的迭代版確實能節(jié)省一些常數(shù)時間這也是競賽常用做法。9. 最后分享一點個人使用體會我最早學(xué)這些算法的時候總覺得最大公約數(shù)和最小公倍數(shù)是面試熱身題沒什么實際用處。后來在寫加密算法、實現(xiàn)分?jǐn)?shù)運算類、處理采樣頻率對齊等實際工程里才發(fā)現(xiàn)gcd和lcm出現(xiàn)的頻率遠(yuǎn)比自己想的高。分?jǐn)?shù)約分需要gcd多個藍(lán)牙設(shè)備的廣播周期對齊需要lcm音視頻編碼中的時間戳對齊也需要lcm。這些東西其實一直在我們身邊只是不專門說“這里用了gcd”而已。另外說個很多教學(xué)文章不會提的小技巧在寫gcd相關(guān)代碼時可以順手封裝一個同時返回gcd和lcm的工具函數(shù)很多場景兩個一起用可以省一次類型轉(zhuǎn)換和一次除法的開銷。代碼很簡單但能體現(xiàn)你對這一塊的掌握程度。理解了這些底層原理之后再看算法題你會發(fā)現(xiàn)很多數(shù)論題目就是在gcd和lcm的組合上套殼。把這一關(guān)打扎實后面看擴(kuò)展歐幾里得、裴蜀定理、模逆元這些進(jìn)階內(nèi)容都會順很多。建議把文中的代碼親手敲一遍再試試用long long跑幾組大數(shù)邊界感受一下什么樣的寫法會爆什么樣的寫法穩(wěn)如老狗。踩過這個坑之后你對這幾個算法的理解就徹底落地了。 最大公約數(shù)與最小公倍數(shù)：更相減損、歐幾里得與Stein算法全解析
看到這個標(biāo)題就很有共鳴最大公約數(shù)和最小公倍數(shù)算是算法入門里最經(jīng)典的一對“老朋友”了。不管是剛學(xué)編程準(zhǔn)備信奧還是刷LeetCode熱身幾乎所有人都會先撞到這幾行代碼。網(wǎng)上講這個的文章很多但大多數(shù)要么只給一個模板要么直接把證明甩你臉上看完能記住的沒幾個。這篇我換個思路把最大公約數(shù)的三種常見算法和最小公倍數(shù)的兩種求法放在一起拆開揉碎講清楚每個算法都交代清楚“為什么能這么算”“邊界在哪”“坑在哪”最后再補(bǔ)上實際工程和競賽里怎么選型的經(jīng)驗。想徹底搞懂這塊內(nèi)容的同學(xué)這篇可以直接收藏。1. 先搞清楚一件事最大公約數(shù)和最小公倍數(shù)的關(guān)系到底是什么很多人把這兩個概念分開記但實際上它們是一對“孿生兄弟”。對于兩個正整數(shù)a和b假設(shè)它們的最大公約數(shù)Greatest Common Divisor簡稱GCD是d最小公倍數(shù)Least Common Multiple簡稱LCM是m那么存在一個非常漂亮的關(guān)系式a × b d × m也就是說兩個數(shù)的乘積等于它們的最大公約數(shù)和最小公倍數(shù)的乘積。這個式子不是湊巧而是有嚴(yán)格數(shù)學(xué)推導(dǎo)的。簡單理解把a(bǔ)和b各自分解成質(zhì)因數(shù)的乘積gcd取的是每個質(zhì)因數(shù)的“較小指數(shù)”lcm取的是每個質(zhì)因數(shù)的“較大指數(shù)”兩者指數(shù)相加正好等于原始的指數(shù)和所以乘起來自然相等。這個關(guān)系式的價值在于求最小公倍數(shù)完全可以借助最大公約數(shù)來實現(xiàn)而最大公約數(shù)的算法在歷史上有過非常多的研究效率高而且穩(wěn)定。所以大部分時候只要會算gcdlcm就等于a / gcd(a, b) * b注意這個計算順序先除后乘可以防止溢出后面會詳細(xì)說。但這不意味著lcm就沒有自己的獨立算法了——直接分解質(zhì)因數(shù)也能求而且某些場景下反而更直觀。接下來我先把最大公約數(shù)的三種經(jīng)典算法講透再說最小公倍數(shù)的兩種求法這樣整個知識體系就閉環(huán)了。2. 最大公約數(shù)算法一更相減損術(shù)——最古老也最直觀的“減法思維”更相減損術(shù)是中國古代數(shù)學(xué)著作《九章算術(shù)》中記載的方法比歐幾里得算法還要早。它的核心思想特別樸素兩個數(shù)的最大公約數(shù)等于“較大的數(shù)減去較小的數(shù)”之后得到的差與“較小的數(shù)”之間的最大公約數(shù)。用數(shù)學(xué)語言表達(dá)就是當(dāng)a b時gcd(a, b) gcd(a - b, b)。這個式子成立的理由也不難理解任何能同時整除a和b的整數(shù)一定能整除它們的差a - b反過來任何能同時整除b和a - b的整數(shù)也一定能整除a因為a (a - b) b。所以公約數(shù)的集合完全一樣最大公約數(shù)自然也一樣。基于這個原理算法流程就是不斷用大數(shù)減小數(shù)直到兩個數(shù)相等這個相等的數(shù)就是最大公約數(shù)。用C實現(xiàn)如下int gcdBySubtraction(int a, int b) { while (a ! b) { if (a b) a - b; else b - a; } return a; }這個算法有個顯而易見的缺點如果兩個數(shù)差距懸殊比如a10000b1那就得循環(huán)減9999次性能極差。但它奠定了“通過不斷縮小問題規(guī)模來解決原問題”的遞歸思想這是后面所有算法的基礎(chǔ)。我在實際講解這個算法的時候喜歡用一個“切繩子”的類比假設(shè)有兩根長度分別為a和b的繩子要找能同時把兩根繩子都切成整數(shù)段的最大長度。更相減損術(shù)的過程就是不停地拿長繩子減短繩子把長繩子替換成剩余的部分直到兩根繩子一樣長。這個“一樣長”的長度就是最大公約數(shù)。說個實操心得更相減損術(shù)雖然效率一般但它在理解“公約數(shù)”本質(zhì)這件事上無可替代。如果你教新手先讓他寫這個再讓他寫歐幾里得算法他對取模運算的理解會深很多。這比直接甩給他一個gcd模板要有效得多。3. 最大公約數(shù)算法二歐幾里得算法輾轉(zhuǎn)相除法——競賽和工程中的絕對主力歐幾里得算法也叫輾轉(zhuǎn)相除法是現(xiàn)在應(yīng)用最廣泛的求最大公約數(shù)算法。它的核心原理和更相減損術(shù)類似但用取模運算代替減法直接實現(xiàn)“大數(shù)換成余數(shù)”gcd(a, b) gcd(b, a mod b)其中a b為什么這樣可以因為取模的本質(zhì)就是連續(xù)減法——a mod b其實就是a不斷減去b直到不夠再減為止。所以歐幾里得算法可以理解為更相減損術(shù)的“批量加速版”一次取模運算相當(dāng)于做了很多次減法。標(biāo)準(zhǔn)遞歸實現(xiàn)int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }迭代實現(xiàn)實際工程中推薦避免遞歸棧開銷int gcdIterative(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return a; }關(guān)于時間復(fù)雜度歐幾里得算法的時間復(fù)雜度是O(log min(a, b))這里log的底數(shù)大約是黃金比例φ ≈ 1.618。也就是說每次取模問題規(guī)模至少縮小一個常數(shù)倍循環(huán)次數(shù)非常少。最壞情況出現(xiàn)在兩個數(shù)是相鄰斐波那契數(shù)時比如gcd(144, 89)循環(huán)次數(shù)達(dá)到最大但那也只是十幾次而已。我在LeetCode刷題時實測過就算a和b都接近int上限約21億循環(huán)次數(shù)也基本不超過45次效率極其穩(wěn)定。這也是為什么所有語言的標(biāo)準(zhǔn)庫幾乎都內(nèi)置了gcd實現(xiàn)C17的std::gcdPython的math.gcd底層基本都用的這個算法。避坑提示遞歸寫法雖然簡潔但面試寫代碼時最好改成迭代。很多遞歸寫法在極端情況下棧深度其實還好因為深度只要幾十層但有些公司的在線評測系統(tǒng)?？臻g設(shè)置得很小萬一遇到類似情況就會無謂地棧溢出。迭代版本的性能更優(yōu)也更能體現(xiàn)你對底層原理的理解。4. 最大公約數(shù)算法三Stein算法二進(jìn)制GCD算法——大整數(shù)場景下的“特種兵”Stein算法是歐幾里得算法的強(qiáng)力補(bǔ)充它拋棄了取模運算只用減法和位運算右移、左移因此在處理超大整數(shù)時優(yōu)勢明顯。為什么拋棄取模呢因為超大整數(shù)比如幾百位的十進(jìn)制數(shù)的除法本身很費時CPU的除法指令周期遠(yuǎn)高于加減法和移位而在高精度計算中“除以2”可以用右移一位完成代價極低。Stein算法的核心規(guī)則基于以下四個觀察如果a和b都是偶數(shù)則gcd(a, b) 2 × gcd(a / 2, b / 2)。如果a是偶數(shù)、b是奇數(shù)則gcd(a, b) gcd(a / 2, b)。如果a是奇數(shù)、b是偶數(shù)則gcd(a, b) gcd(a, b / 2)。如果a和b都是奇數(shù)則gcd(a, b) gcd((a - b) / 2, b)利用更相減損術(shù)的原理。遞歸終止條件是a b此時gcd就是a也是b。C實現(xiàn)int gcdStein(int a, int b) { if (a 0) return b; if (b 0) return a; int shift 0; // 提取公共的因子2 while (((a | b) 1) 0) { a 1; b 1; shift; } // 確保a是奇數(shù) while ((a 1) 0) a 1; while (b ! 0) { while ((b 1) 0) b 1; if (a b) swap(a, b); b - a; } return a shift; }這段代碼看起來比歐幾里得算法復(fù)雜但核心思想就是“不斷消去因子2把兩個奇數(shù)的情況轉(zhuǎn)換成減法再除以2”。每次循環(huán)至少把一個數(shù)縮半整體時間復(fù)雜度仍然是O(log max(a, b))級別。適用場景說明普通int范圍內(nèi)的gcdStein算法相比歐幾里得算法并沒有明顯優(yōu)勢有時甚至稍慢因為邏輯分支更多。但在以下場景中Stein算法才是真正的王者高精度大整數(shù)計算大數(shù)取模一次的成本極其高昂而“除以2”只需要在高精度數(shù)組的首位處理一下成本低得驚人。嵌入式等對除法指令敏感的環(huán)境某些低端MCU沒有硬件除法指令取模運算通過軟件模擬會非常慢Stein算法全程只用減法和移位優(yōu)勢巨大。密碼學(xué)中的大數(shù)運算RSA等算法需要大量gcd計算其中操作數(shù)往往有幾百上千比特。從工程實踐角度看如果你只需要在普通程序里求gcd直接用歐幾里得算法沒錯但如果你在做大數(shù)運算庫或者對性能敏感的系統(tǒng)級開發(fā)Stein算法是你必須掌握的備選方案。5. 最小公倍數(shù)求法一利用gcd公式法——最通用、最推薦的方案前面提到過關(guān)鍵公式lcm(a, b) a / gcd(a, b) * b。這個式子用起來很簡單但有一個非常容易踩的坑先乘a × b再除以gcd在大數(shù)場景下會溢出。舉個例子a2^31 - 1int最大值b2^31 - 2兩者乘積大約是4.6×10^18遠(yuǎn)超int的表示范圍約2.1×10^9直接乘必然溢出。所以標(biāo)準(zhǔn)寫法一定是先除后乘int lcm(int a, int b) { return a / gcd(a, b) * b; }這樣做的數(shù)學(xué)依據(jù)a / gcd(a, b)和b互為“互質(zhì)部分”的關(guān)系兩者相乘不會超出a和b乘積的理論值但在很多情況下不會溢出。什么情況下還是會溢出呢答案是當(dāng)a和b本身就是接近極限的大整數(shù)時它們的lcm可能超出int范圍以int類型存儲無論如何都會溢出。這時就需要升級為long long或大整數(shù)類型而不能只靠調(diào)整運算順序來規(guī)避。C標(biāo)準(zhǔn)庫風(fēng)格的完整實現(xiàn)#include numeric #include algorithm long long lcm_ll(long long a, long long b) { return a / std::gcd(a, b) * b; }實操心得在競賽中處理多組數(shù)據(jù)的LCM時我習(xí)慣將a和b統(tǒng)一提升為long long再做運算并且全程使用long long保存中間結(jié)果。很多同學(xué)一開始用int存gcd的結(jié)果然后轉(zhuǎn)成long long乘結(jié)果還是溢出——因為溢出發(fā)生在int乘法階段已經(jīng)來不及了。正確做法是從頭到尾都用更大的類型。另外這個公式還有一個漂亮的性質(zhì)求多個數(shù)的lcm可以兩兩迭代計算。比如求lcm(a, b, c)可以先算lcm_ab lcm(a, b)再算lcm(lcm_ab, c)。但要注意計算過程中數(shù)值可能增長得很快所以務(wù)必使用更大范圍的數(shù)據(jù)類型每算一步都盡量先除后乘。6. 最小公倍數(shù)求法二分解質(zhì)因數(shù)法——直觀但代價更高的路徑第二種求lcm的辦法是從定義出發(fā)先把每個數(shù)分解成質(zhì)因數(shù)的冪次積然后對每個質(zhì)因數(shù)取“所有數(shù)中出現(xiàn)的最大指數(shù)”再乘起來。舉個例子求lcm(12, 18)12 22 × 3118 21 × 32對質(zhì)因數(shù)2取最大指數(shù)2對質(zhì)因數(shù)3取最大指數(shù)2所以 lcm 22 × 32 36。這種方法的直觀性極強(qiáng)特別適合用來向初學(xué)者解釋“最小公倍數(shù)到底最小在哪”每個質(zhì)因數(shù)的指數(shù)都不能小于任何一個數(shù)中該質(zhì)因數(shù)的指數(shù)否則無法整除對應(yīng)數(shù)而“最小”意味著恰好取到這些最大指數(shù)一個不多一個不少。算法實現(xiàn)上需要先準(zhǔn)備素數(shù)表可以用埃氏篩或歐拉篩然后對每個數(shù)做質(zhì)因數(shù)分解記錄每個質(zhì)因數(shù)的最大出現(xiàn)次數(shù)#include vector #include map std::vectorint sieve(int n) { std::vectorbool is_prime(n 1, true); std::vectorint primes; is_prime[0] is_prime[1] false; for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); for (int j i * i; j n; j i) { is_prime[j] false; } } } return primes; } long long lcmByFactorization(int a, int b) { std::mapint, int max_exp; // 對a分解質(zhì)因數(shù) int x a; for (int p 2; p * p x; p) { int cnt 0; while (x % p 0) { x / p; cnt; } if (cnt 0) max_exp[p] cnt; } if (x 1) max_exp[x] 1; // 對b分解質(zhì)因數(shù)并更新最大指數(shù) int y b; for (int p 2; p * p y; p) { int cnt 0; while (y % p 0) { y / p; cnt; } if (cnt max_exp[p]) max_exp[p] cnt; } if (y 1) max_exp[y] std::max(max_exp[y], 1); long long result 1; for (auto [p, e] : max_exp) { while (e--) result * p; } return result; }這種實現(xiàn)明顯比gcd公式法復(fù)雜時間復(fù)雜度也高不少——單次分解質(zhì)因數(shù)最壞情況是O(√n)再加上篩法建表的開銷在大數(shù)據(jù)量下性能遠(yuǎn)不如歐幾里得算法。但它的優(yōu)勢在于可解釋性和可擴(kuò)展性當(dāng)你需要一次性求多個數(shù)的最小公倍數(shù)并且要輸出分解過程比如數(shù)學(xué)題解題過程、教學(xué)演示這個方法無可替代。另外如果你已經(jīng)維護(hù)了一套質(zhì)因數(shù)分解系統(tǒng)順帶求lcm就是“免費”的不用額外維護(hù)新的邏輯。7. 三種GCD算法與兩種LCM求法的全面對比與選型建議我把上面幾種算法放在一起做一次橫向?qū)Ρ冗@樣選型的時候一眼就能看清楚算法核心運算時間復(fù)雜度代碼復(fù)雜度最佳適用場景更相減損術(shù)減法最壞O(max(a,b))極簡教學(xué)演示、理解公約數(shù)概念歐幾里得算法取模O(log min(a,b))簡潔通用場景、競賽刷題、標(biāo)準(zhǔn)庫實現(xiàn)Stein算法減法移位O(log max(a,b))中等超大整數(shù)、無除法硬件環(huán)境分解質(zhì)因數(shù)法求LCM質(zhì)因數(shù)分解O(√n)較復(fù)雜數(shù)學(xué)解題演示、多數(shù)組件化求LCMgcd公式法求LCM除法乘法O(log min(a,b))極簡幾乎一切工程場景首選方案選型建議默認(rèn)情況下的最優(yōu)解非常明確——最大公約數(shù)用歐幾里得算法最小公倍數(shù)用“先除后乘”的gcd公式法。這組合在時間效率、代碼可維護(hù)性、防溢出安全性上都做到最優(yōu)。但在以下場景需要重新考慮教學(xué)場景優(yōu)先用更相減損術(shù)分解質(zhì)因數(shù)法。雖然性能一般但學(xué)生能直觀看到“公約數(shù)”是如何從“不斷相減”中浮現(xiàn)的比直接給代碼要有說服力得多。大整數(shù)運算場景改用Stein算法。尤其在做高精度庫如大數(shù)RSA、密碼學(xué)算法時取模是性能殺手減法和移位才有優(yōu)勢。如果你計算的是浮點數(shù)或需要處理不一定為整數(shù)的情況gcd和lcm都只適用于整數(shù)這些算法全部作廢。請先回到問題定義確認(rèn)數(shù)據(jù)是整數(shù)再做方案選型。對于剛?cè)腴T的朋友我建議先把歐幾里得算法背得滾瓜爛熟然后自己手寫一遍迭代版和遞歸版再分別測試幾組大數(shù)對比運行時間。等你對取模的循環(huán)過程有了手感再去看Stein算法和更相減損術(shù)會發(fā)現(xiàn)它們之間的演進(jìn)關(guān)系非常自然。8. 常見問題與排查技巧實錄這塊整理我在教學(xué)和刷題過程中經(jīng)常遇到的典型問題每個都是真實踩過的坑問題1遞歸版gcd在數(shù)據(jù)很大時會棧溢出嗎不會。歐幾里得算法遞歸深度不超過O(log min(a, b))即使a、b均為max long long深度也只有幾十層離棧溢出很遠(yuǎn)。但如果你的遞歸函數(shù)寫得不小心比如每次遞歸前就復(fù)制了巨大的對象比如大整數(shù)的vector數(shù)組那棧和堆都有風(fēng)險。所以競賽中我一般直接寫迭代版不給自己留隱患。問題2用lcm(a,b) a * b / gcd(a,b)到底行不行數(shù)學(xué)上完全正確但工程上不推薦。因為a * b在int范圍內(nèi)極容易溢出而a / gcd(a, b) * b就能在很大范圍內(nèi)安全計算。我見過太多人因為這種寫法在LeetCode第1201題這類題目上交了錯誤答案調(diào)試半天才發(fā)現(xiàn)是溢出。養(yǎng)成先除后乘的習(xí)慣以后這類問題可以幾乎絕跡。問題3求0和某個數(shù)的gcd、lcm會發(fā)生什么gcd(0, n) n這是數(shù)學(xué)上的約定但lcm(0, n)嚴(yán)格來說是未定義的因為0沒有“倍數(shù)”概念。實際工程中如果你用a / gcd * b去算gcd為0時直接觸發(fā)除零錯誤所以要么提前處理a或b為0的情況要么約定輸入為正整數(shù)。在刷題時也要先看題目約束條件大多數(shù)題目明確說“a和b均為正整數(shù)”這時候就不用擔(dān)心這個問題。問題4更相減損術(shù)碰上懸殊數(shù)字算得很慢怎么區(qū)分“教學(xué)價值高”和“實際不可用”我的經(jīng)驗是更相減損術(shù)適合在小范圍數(shù)據(jù)或課堂教學(xué)中使用一旦數(shù)據(jù)超過一萬量級性能問題就會非常突出。如果在競賽題里看到需要計算gcd且數(shù)據(jù)范圍很大直接放棄更相減損術(shù)上歐幾里得不要有心理負(fù)擔(dān)。理解它的原理就夠了不意味著必須在所有場景用它。問題5多個數(shù)的gcd和lcm有沒有什么優(yōu)化技巧多個數(shù)的gcd就是從頭到尾兩兩迭代gcd順序不影響結(jié)果lcm同樣兩兩迭代但注意結(jié)果是“越迭代越大”所以如果題目的最終要求是取模輸出最好在迭代過程中每步都取模防止中間結(jié)果爆炸。比如求n個數(shù)lcm對某個mod取模可以每次lcm算完直接 % mod但如果后續(xù)還要用這個lcm去求別的數(shù)就不能只保存取模后的值而應(yīng)該用適當(dāng)?shù)拇髷?shù)類型保存完整結(jié)果。這個細(xì)節(jié)在題目“求n個數(shù)的lcm對mod取模”中經(jīng)常出現(xiàn)需要根據(jù)題目要求靈活處理。問題6為什么標(biāo)準(zhǔn)庫的std::gcd有時比手寫慢標(biāo)準(zhǔn)庫實現(xiàn)通常會處理更多邊界情況包括負(fù)數(shù)、類型轉(zhuǎn)換等并且開啟了異常檢查所以可能比手寫簡單版本稍慢。但這差別微乎其微工程中完全沒有必要因此放棄標(biāo)準(zhǔn)庫。不過在處理超高頻率調(diào)用gcd的算法題目時比如某些數(shù)論題中循環(huán)幾十萬次手寫一個不帶邊檢的迭代版確實能節(jié)省一些常數(shù)時間這也是競賽常用做法。9. 最后分享一點個人使用體會我最早學(xué)這些算法的時候總覺得最大公約數(shù)和最小公倍數(shù)是面試熱身題沒什么實際用處。后來在寫加密算法、實現(xiàn)分?jǐn)?shù)運算類、處理采樣頻率對齊等實際工程里才發(fā)現(xiàn)gcd和lcm出現(xiàn)的頻率遠(yuǎn)比自己想的高。分?jǐn)?shù)約分需要gcd多個藍(lán)牙設(shè)備的廣播周期對齊需要lcm音視頻編碼中的時間戳對齊也需要lcm。這些東西其實一直在我們身邊只是不專門說“這里用了gcd”而已。另外說個很多教學(xué)文章不會提的小技巧在寫gcd相關(guān)代碼時可以順手封裝一個同時返回gcd和lcm的工具函數(shù)很多場景兩個一起用可以省一次類型轉(zhuǎn)換和一次除法的開銷。代碼很簡單但能體現(xiàn)你對這一塊的掌握程度。理解了這些底層原理之后再看算法題你會發(fā)現(xiàn)很多數(shù)論題目就是在gcd和lcm的組合上套殼。把這一關(guān)打扎實后面看擴(kuò)展歐幾里得、裴蜀定理、模逆元這些進(jìn)階內(nèi)容都會順很多。建議把文中的代碼親手敲一遍再試試用long long跑幾組大數(shù)邊界感受一下什么樣的寫法會爆什么樣的寫法穩(wěn)如老狗。踩過這個坑之后你對這幾個算法的理解就徹底落地了。