教程文檔知識(shí)庫【免費(fèi)下載鏈接】AlgoNote??「算法通關(guān)手冊(cè)」從零開始的「算法與數(shù)據(jù)結(jié)構(gòu)」學(xué)習(xí)教程200 道「算法面試熱門題目」1000 道「LeetCode 題目解析」持續(xù)更新中項(xiàng)目地址https://gitcode.com/gh_mirrors/le/AlgoNote點(diǎn)擊查看免費(fèi)下載本篇技術(shù)指南基于「算法通關(guān)手冊(cè)」倉(cāng)庫中的 0172. 階乘后的零題解 展開系統(tǒng)講解如何利用數(shù)論中「因子分解」的思路在 O(log n) 時(shí)間內(nèi)求出n!末尾零的個(gè)數(shù)。讀完本文你將掌握「尾隨零」類題目的統(tǒng)一解法模型并理解它與倉(cāng)庫內(nèi) 面試題 16.05. 階乘尾數(shù)、0793. 階乘函數(shù)后 K 個(gè)零 等同類題目的遞進(jìn)關(guān)系。題目信息題號(hào)0172題目階乘后的零Factorial Trailing Zeroes標(biāo)簽數(shù)學(xué)難度中等題解文檔factorial-trailing-zeroes.md題目大意給定一個(gè)整數(shù)n要求返回n!即n的階乘結(jié)果中尾隨零trailing zeroes的數(shù)量。約束條件$$0 \le n \le 10^4$$由于n最大可達(dá)10^4n!是一個(gè)擁有數(shù)萬個(gè)數(shù)字位的超長(zhǎng)整數(shù)任何「先算階乘再數(shù)零」的直接做法都會(huì)面臨溢出或大數(shù)計(jì)算開銷過大的問題因此必須從數(shù)學(xué)角度尋找規(guī)律。核心數(shù)學(xué)原理尾隨零從何而來在十進(jìn)制中一個(gè)數(shù)字每乘上10末尾就會(huì)多一個(gè)0。而$$10 2 \times 5$$因此n!末尾零的個(gè)數(shù)等價(jià)于1 × 2 × 3 × ... × n這個(gè)連乘結(jié)果中能組成多少個(gè)(2, 5)因子對(duì)。由于每一對(duì)2 × 5都能貢獻(xiàn)一個(gè)因子10所以尾隨零的個(gè)數(shù) min(因子 2 的個(gè)數(shù), 因子 5 的個(gè)數(shù))接下來是一個(gè)關(guān)鍵的觀察在從1到n的所有整數(shù)中因子 2 的個(gè)數(shù)永遠(yuǎn)不少于因子 5 的個(gè)數(shù)。為什么因?yàn)榕紨?shù)每隔2個(gè)就會(huì)出現(xiàn)一次貢獻(xiàn)一個(gè)2而5的倍數(shù)每隔5個(gè)才出現(xiàn)一次。例如在1 ~ 10中整數(shù)質(zhì)因子分解因子 2 的個(gè)數(shù)因子 5 的個(gè)數(shù)42220550182330102 × 511直觀上由于2 5在任意前綴1 ~ n中「包含因子 2 的整數(shù)」出現(xiàn)得更頻繁、更密集累計(jì)貢獻(xiàn)的2因子數(shù)量一定大于等于累計(jì)貢獻(xiàn)的5因子數(shù)量。所以上式中的min恒等于因子 5 的個(gè)數(shù)。于是原問題被轉(zhuǎn)化為一個(gè)更簡(jiǎn)單的問題求n!中質(zhì)因子5的總個(gè)數(shù)。這也是整個(gè)題解factorial-trailing-zeroes.md的核心結(jié)論「尾隨 0 的個(gè)數(shù)為 2 的倍數(shù)個(gè)數(shù)和 5 的倍數(shù)個(gè)數(shù)的最小值又因?yàn)?2 52 的倍數(shù)個(gè)數(shù)肯定小于等于 5 的倍數(shù)所以直接統(tǒng)計(jì) 5 的倍數(shù)個(gè)數(shù)即可?！菇y(tǒng)計(jì)公式勒讓德公式Legendres Formula的階乘版本「統(tǒng)計(jì)n!中質(zhì)因子5的總個(gè)數(shù)」聽起來簡(jiǎn)單但要小心一個(gè)陷阱不僅僅是5的倍數(shù)在貢獻(xiàn)因子 5。以n 25為例5, 10, 15, 20, 25是5的倍數(shù)共5個(gè)貢獻(xiàn) 5 個(gè)因子5但其中25 52本身含有兩個(gè)因子 5上述統(tǒng)計(jì)只算了 1 個(gè)少算了 1 個(gè)。因此需要一層一層地「剝洋蔥」先統(tǒng)計(jì)n以內(nèi)所有5的倍數(shù)個(gè)數(shù)?n / 5?再統(tǒng)計(jì)所有25的倍數(shù)個(gè)數(shù)它們額外多貢獻(xiàn)一個(gè) 5?n / 25?再統(tǒng)計(jì)所有125的倍數(shù)個(gè)數(shù)?n / 125?以此類推直到5^k n為止。最終公式為$$f(n) \left\lfloor \frac{n}{5} \right\rfloor \left\lfloor \frac{n}{25} \right\rfloor \left\lfloor \frac{n}{125} \right\rfloor \cdots \sum_{k1}^{\infty} \left\lfloor \frac{n}{5^k} \right\rfloor$$這就是統(tǒng)計(jì)n!中某個(gè)質(zhì)因子個(gè)數(shù)的通用公式勒讓德公式。以n 25驗(yàn)證$$f(25) \lfloor 25/5 \rfloor \lfloor 25/25 \rfloor \lfloor 25/125 \rfloor 5 1 0 6$$而25! 15511210043330985984000000末尾確實(shí)有 6 個(gè)零驗(yàn)證通過。代碼實(shí)現(xiàn)與逐行解析倉(cāng)庫題解給出的 Python 實(shí)現(xiàn)如下factorial-trailing-zeroes.mdclass Solution: def trailingZeroes(self, n: int) - int: count 0 while n 0: count n // 5 n n // 5 return count這段代碼將上面公式中的「每一層?n / 5^k?」壓縮成了循環(huán)行號(hào)操作作用3count 0初始化計(jì)數(shù)器4while n 0循環(huán)直到n 5此時(shí)?n / 5? 0更高次冪項(xiàng)也為 0可以停止5count n // 5累加當(dāng)前這一層5^k的倍數(shù)個(gè)數(shù)6n n // 5將n縮小 5 倍等價(jià)于進(jìn)入下一層k 1正確性推導(dǎo)循環(huán)第 1 輪累加?n/5?第 2 輪累加?n/25?第 3 輪累加?n/125?……恰好逐項(xiàng)復(fù)現(xiàn)公式直到某輪n 5后所有項(xiàng)均為 0 而退出與公式完全等價(jià)。邊界情況n 00! 1末尾沒有零循環(huán)體不執(zhí)行返回0正確n 1 ~ 4階乘值分別為1, 2, 6, 24均無尾隨零n // 5 0返回0正確n 55! 120尾隨零為 1循環(huán)第 1 輪count 1n 1第 2 輪count 1n 0返回 1正確。復(fù)雜度分析時(shí)間復(fù)雜度$O(\log_5 n)$。每輪循環(huán)n除以5循環(huán)次數(shù)為 $\log_5 n$ 量級(jí)。當(dāng)n 10^4時(shí)僅需約 $\log_5 10^4 \approx 6$ 輪幾乎可以視為常數(shù)時(shí)間。空間復(fù)雜度$O(1)$。只使用了單個(gè)整數(shù)變量count不依賴任何額外數(shù)據(jù)結(jié)構(gòu)。相比「直接計(jì)算n!再統(tǒng)計(jì)末尾零」的方案——其時(shí)間復(fù)雜度為 $O(n)$ 且需要處理超大整數(shù)——本解法在時(shí)間上是指數(shù)級(jí)的提升同時(shí)徹底規(guī)避了溢出問題。手動(dòng)推演示例用幾個(gè)典型輸入走一遍算法加深理解示例 1n 1010! 3628800尾隨零為 2。循環(huán)輪次當(dāng)前 n累加值 n // 5累計(jì) count第 1 輪1022第 2 輪202計(jì)算過程?10/5? ?10/25? 2 0 2正確。示例 2n 100100!的尾隨零為 24。循環(huán)輪次當(dāng)前 n累加值 n // 5累計(jì) count第 1 輪1002020第 2 輪20424第 3 輪4024計(jì)算過程?100/5? ?100/25? ?100/125? 20 4 0 24其中25, 50, 75, 100四個(gè)數(shù)各多貢獻(xiàn)了一個(gè) 5正確。示例 3n 125循環(huán)輪次當(dāng)前 n累加值 n // 5累計(jì) count第 1 輪1252525第 2 輪25530第 3 輪5131第 4 輪1031125 53自身貢獻(xiàn)了 3 個(gè)因子 5因此結(jié)果31比「125 以內(nèi) 5 的倍數(shù)個(gè)數(shù) 25」多出 6 個(gè)全部來自25與125的更高次冪項(xiàng)正確。一題多解視角與同類題延伸這道題的解法屬于數(shù)學(xué)推導(dǎo)型題目核心方法論可歸納為三步建立映射末尾零 → 因子 10 → 因子對(duì)(2, 5)化簡(jiǎn)問題利用2因子恒富余的性質(zhì)把問題轉(zhuǎn)化為只統(tǒng)計(jì)5因子逐層統(tǒng)計(jì)用?n/5? ?n/25? ?n/125? ...精確計(jì)數(shù)?！杆惴ㄍP(guān)手冊(cè)」倉(cāng)庫中與該題直接相關(guān)的姊妹題目還有面試題 16.05. 階乘尾數(shù)題目要求與 0172 完全一致被歸入「面試題」系列同樣采用統(tǒng)計(jì) 5 的倍數(shù)個(gè)數(shù)的解法可作為本題的鏡像練習(xí)0793. 階乘函數(shù)后 K 個(gè)零困難難度將本題的結(jié)論f(x)x!末尾零個(gè)數(shù)抽象成單調(diào)函數(shù)再利用二分查找求解滿足f(x) k的x個(gè)數(shù)是本題數(shù)學(xué)結(jié)論的高級(jí)應(yīng)用。這三道題在倉(cāng)庫中形成了「基礎(chǔ)題 → 面試題 → 進(jìn)階題」的完整學(xué)習(xí)鏈路均可通過題解匯總目錄 docs/solutions/index.md 與 00_05_solutions_list.md 檢索定位。小結(jié)LeetCode 0172「階乘后的零」是一道經(jīng)典的數(shù)論入門題考察的核心能力是質(zhì)因子分解與計(jì)數(shù)。它的關(guān)鍵結(jié)論——尾隨零個(gè)數(shù)等于n!中因子 5 的個(gè)數(shù)——不僅能在 $O(\log n)$ 時(shí)間內(nèi)直接給出答案更是解決 0793「階乘函數(shù)后 K 個(gè)零」等進(jìn)階問題的基礎(chǔ)工具。建議讀者在掌握本題后繼續(xù)完成倉(cāng)庫中 面試題 16.05 的獨(dú)立編寫并嘗試閱讀 0793 題解 中二分查找與本題結(jié)論結(jié)合的設(shè)計(jì)思路從而徹底吃透「尾隨零」這一題型。贊分享教程文檔知識(shí)庫【免費(fèi)下載鏈接】AlgoNote??「算法通關(guān)手冊(cè)」從零開始的「算法與數(shù)據(jù)結(jié)構(gòu)」學(xué)習(xí)教程200 道「算法面試熱門題目」1000 道「LeetCode 題目解析」持續(xù)更新中項(xiàng)目地址https://gitcode.com/gh_mirrors/le/AlgoNote點(diǎn)擊查看免費(fèi)下載相關(guān)推薦LeetCode 172 Factorial Trailing Zeroes 題解數(shù)論推導(dǎo)「階乘后的零」的 O(log n) 解法LeetCode 172 Factorial Trailing Zeroes 題解數(shù)論推導(dǎo)「階乘后的零」的 O log n 解法 本篇技術(shù)指南以 leetco文檔教程知識(shí)庫LeetCode 172 階乘后的零Factorial Trailing Zeroes數(shù)論推導(dǎo)與 O(log n) 解法全解析LeetCode 172 階乘后的零Factorial Trailing Zeroes數(shù)論推導(dǎo)與 O log n 解法全解析 本篇技術(shù)指南圍繞 leetc文檔教程知識(shí)庫LeetCode-Go 精講172. Factorial Trailing Zeroes 階乘尾隨零的數(shù)學(xué)推導(dǎo)與 O(log n) Go 實(shí)現(xiàn)LeetCode Go 精講172. Factorial Trailing Zeroes 階乘尾隨零的數(shù)學(xué)推導(dǎo)與 O log n Go 實(shí)現(xiàn) 導(dǎo)讀本文以 L示例工程上一篇免費(fèi)開源的Nigate三步讓Mac讀寫NTFS硬盤跨平臺(tái)傳文件不再求人下一篇EdgeRemover 實(shí)戰(zhàn)教程1 分鐘徹底卸載 Windows 10/11 的 Microsoft Edge創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考