第一次看到793題的時候我盯著題目看了兩分鐘第一反應(yīng)是這題和二分有什么關(guān)系階乘、尾零、K三個詞放在一起像是一道背結(jié)論的數(shù)學(xué)題。等我把“二分答案”四個字重新讀進(jìn)腦子才反應(yīng)過來真正的考點其實不在階乘怎么算而在“怎么把一個求個數(shù)的問題變成一個在值域上二分查找的問題”。這道題的全名很長——階乘函數(shù)后 K 個零刷過在線題庫的應(yīng)該都見過編號是793。題面一句話給定非負(fù)整數(shù)K問有多少個非負(fù)整數(shù)n滿足 n! 的末尾恰好有 K 個零。很多人一上來就慌了因為n可以巨大K最大能到1e9直接枚舉n肯定不行。但這道題恰恰是“二分答案”這一套路里特別經(jīng)典的入門題練好它對后面啃第K小、第K大類題目幫助很大。1. 先搞懂題目到底在問什么1.1 階乘尾零是怎么算出來的n! 的末尾有多少個零本質(zhì)是在問“n! 這個數(shù)因子10出現(xiàn)了多少次”。10 2 × 5所以只要數(shù)一數(shù)n!的質(zhì)因子分解里有幾對2和5尾零就有幾個。這里有個關(guān)鍵直覺2的個數(shù)永遠(yuǎn)比5多。1到n之間每兩個數(shù)才有一個偶數(shù)但每五個數(shù)才有一個5的倍數(shù)理論上前者出現(xiàn)的頻率遠(yuǎn)高于后者。所以尾零的個數(shù)完全由因子5的個數(shù)決定我們只需要統(tǒng)計1到n中所有數(shù)一共貢獻(xiàn)了多少個質(zhì)因子5。怎么數(shù)用除法連除累加零的個數(shù) f(n) n/5 n/25 n/125 ...為什么這么加n/5 表示1到n中有多少個5的倍數(shù)每個至少貢獻(xiàn)一個5但像25、50、75這類數(shù)本身有兩個5因子第二個5因子被漏掉了所以再加 n/25同理125有三個5因子前兩步只統(tǒng)計了兩個于是再加 n/125一直加到商為0為止?？磧蓚€小例子。10! 3628800末尾2個零。用公式算10/5 210/25 0總數(shù)為2正確。25!末尾6個零。公式算25/5 525/25 125/125 0總數(shù)為6。手算也能驗證25這個數(shù)內(nèi)部就藏了2個5因子所以比f(24)多跳了2。這個公式和實現(xiàn)都不復(fù)雜復(fù)雜的是“知道有公式之后接下來怎么用它”。1.2 尾零個數(shù)序列的真實長相平臺、跳躍與單調(diào)按n從小到大把f(n)列出來你會看到一段很有意思的序列n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... f 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 3 ...規(guī)律很明顯f(n)是單調(diào)不減的n變大尾零數(shù)只會增加或持平不會減少。連續(xù)5個數(shù)往往共享同一個f值。因為同樣尾零數(shù)量會一直持續(xù)到下一個5的倍數(shù)之前平臺寬度最多是5。每到5的倍數(shù)值會往上跳但有時跳1有時跳更多。比如f(24)4但f(25)6直接跳過5這個值。這里有一層容易忽略的信息既然f(n)會跳檔那么K5這種值就找不到任何n對應(yīng)它。題目問“有多少個n滿足f(n)K”答案完全可能是0。這不是特殊情況而是這道題的常態(tài)。想通這條序列后面寫二分時才能明白為什么要找左邊界和右邊界。2. 為什么這題要二分“答案”而不是二分“下標(biāo)”2.1 單調(diào)性是二分答案的入場券很多同學(xué)一提到二分腦子里只有“給一個有序數(shù)組二分查找某個元素”。但二分真正的價值在于只要一個函數(shù)在定義域上是單調(diào)的我們就可以在值域上做查找而不需要精確知道函數(shù)長什么樣。f(n)滿足非嚴(yán)格單調(diào)遞增這是一個非常好的性質(zhì)?，F(xiàn)在問題變成了給定K找到所有“通過f(n)映射等于K”的n。我們完全可以拿mid當(dāng)自變量算f(mid)然后比較f(mid)和K的大小關(guān)系。如果f(mid) K說明n取小了左邊界往右挪如果f(mid) K說明有可能已經(jīng)進(jìn)入“等于K”的區(qū)域就往左收縮找更小的可行位置。整個過程不是直接枚舉n而是通過二分不斷逼近邊界。這就像在字典里找一個姓氏的頁碼范圍不用一頁頁翻先翻中間看首字母比目標(biāo)大了還是小了然后不斷縮小區(qū)間。2.2 第K小/第K大問題的通用思考框架把793題掛上“二分答案”的標(biāo)簽是因為它和一類更高頻的題目共用同一套思想第K小或第K大。這類題目有個共同特征直接排序所有候選值往往做不到因為候選值的數(shù)量可能大到無法枚舉但判定“有多少個值小于等于mid”卻很容易。經(jīng)典套路如下確定候選值的范圍[lo, hi]這通常是整個數(shù)據(jù)的最小值和最大值。取mid lo (hi - lo) / 2寫一個判定函數(shù) cnt(mid)統(tǒng)計滿足條件比如小于等于mid的候選值個數(shù)。如果 cnt(mid) K說明第K小的候選值不會比mid更大收縮右邊界 hi mid。否則說明第K小候選值至少比mid大收縮左邊界 lo mid 1。最終lo停下的位置就是第K小。這其實是“二分答案”的通用骨架。第K大可以換個方向或者數(shù)學(xué)上轉(zhuǎn)化成第總數(shù)-K1小本質(zhì)一模一樣。為什么大家愿意用二分答案因為判定函數(shù)往往只要O(N)掃一遍甚至像793題只需要O(logN)而候選值域再大二分也就幾十次迭代。這種收益在數(shù)據(jù)量大的時候極其明顯。2.3 793問的不是第K小為什么也歸到這里嚴(yán)格來說793題問的不是“第K小是什么”而是“有多少個數(shù)的函數(shù)值等于K”。但它依然落在“二分答案”這個分類里原因是我們要在n的值域上找到滿足 f(n) K 的區(qū)間端點。換句話說題目問的是這個區(qū)間的長度而區(qū)間端點必須靠二分找。你無法用普通二分“找到K然后往兩邊擴(kuò)展”的辦法因為n可能到4e9量級線性擴(kuò)展會直接超時。正確做法是第一次二分找“第一個f(n) K”的位置這是左端點。第二次二分找“第一個f(n) K”的位置再減1這是右端點。兩個端點一減加1就是答案。這比單純的“求第K小”多了一點點變化但底層邏輯完全相通利用單調(diào)性把問題歸結(jié)為找邊界。3. 二分邊界怎么定5K到底夠不夠3.1 上界選取與證明寫二分前先解決一個大問題n的范圍到底設(shè)到多少題目給出的K最大是1e9。f(n)的漸近形態(tài)可以這樣估算f(n) n/5 n/25 n/125 ... ≈ n/4這是因為首項1/5后面每項是前一項除以5等比求和極限正好是1/4。所以要讓f(n)達(dá)到Kn大約需要4K。為了保險二分上界取h 5*K基本足夠。之所以說“基本”最好是證明一下對任意正整數(shù)K令n 5K那么f(5K) K K/5 K/25 ...這個值一定不小于K。這就說明在區(qū)間[0, 5K]內(nèi)一定能找到f(n)至少為K的位置左端點二分不會跑空。對K0時區(qū)間[0,0]也完全沒有問題。這里的細(xì)節(jié)是類型。K本身是int但5*K當(dāng)K1e9時達(dá)到5e9早就超出32位int的范圍。所以上界必須用long long存不然大概率會出現(xiàn)負(fù)數(shù)邊界二分直接崩掉。很多第一次寫這題的人就是栽在這一步。3.2 兩次二分的寫法第一次二分找左邊界l 0 r 5 * K while l r: mid (l r) / 2 if trailingZeroes(mid) K: r mid else: l mid 1這個模板的語義是不斷壓低右邊界找到第一個滿足“尾零數(shù)K”的n存到l。第二次二分找右邊界l 0 r 5 * K while l r: mid (l r) / 2 if trailingZeroes(mid) K: r mid else: l mid 1它找的是第一個“尾零數(shù)大于K”的n找到后減1就是最后一個“尾零數(shù)等于K”的位置。有人會問為什么第一個找“”第二個找“”因為我們要的區(qū)間左閉右開。第二個位置本身不屬于答案屬于右邊第一個超出區(qū)間的點。兩次二分用的是同一個值域判定條件差一個等號這就是區(qū)間端點二分的標(biāo)準(zhǔn)姿勢。3.3 完整C實現(xiàn)下面給一份可以直接跑通的代碼注釋寫在關(guān)鍵位置方便對照理解class Solution { public: int preimageSizeFZF(int K) { // 上界取5*KK最大1e9時不會超過long long范圍 long long left 0, right 5LL * K; // 第一次二分找第一個 f(n) K 的位置 long long l left, r right; while (l r) { long long mid l (r - l) / 2; if (trailingZeroes(mid) K) { r mid; } else { l mid 1; } } long long lo l; // 如果這個位置算出來的尾零數(shù)不等于K說明K被跳過了直接返回0 if (trailingZeroes(lo) ! K) { return 0; } // 第二次二分找第一個 f(n) K 的位置 l left, r right; while (l r) { long long mid l (r - l) / 2; if (trailingZeroes(mid) K) { r mid; } else { l mid 1; } } long long hi l - 1; return hi - lo 1; } long long trailingZeroes(long long n) { long long count 0; while (n 0) { n / 5; count n; } return count; } };這里我做了一個小優(yōu)化如果第一次二分結(jié)束lo位置的f(lo)不等于K說明K這個值根本不存在直接返回0沒必要再跑第二次二分。這個優(yōu)化雖然小但能讓無解分支的速度快一倍。4. 常見坑點與調(diào)試實錄4.1 溢出不是小問題剛開始寫這題的某同學(xué)第一次提交用int存二分上界K傳1e9的時候5*K直接變成了負(fù)的二分區(qū)間完全錯亂。當(dāng)時他把trailingZeroes函數(shù)也寫成int型n/5累加在大數(shù)下溢出結(jié)果跑了幾個樣例全錯。這是個特別容易忽略的點只要N的范圍允許到5e9那么所有跟n打交道的位置都要用long long。判定函數(shù)的參數(shù)、返回值和臨時變量全部要帶類型。我見過不少人只把right改成long long但trailingZeroes里還在用int接收參數(shù)照樣錯。4.2 死循環(huán)與mid取整二分模板里有人習(xí)慣寫mid (l r 1) / 2有人習(xí)慣寫mid (l r) / 2。這兩種對應(yīng)不同的邊界更新習(xí)慣。在這個題里兩個二分都是“左邊界向右側(cè)收縮”的模式用下取整不會死循環(huán)。因為當(dāng)l r時mid (lr)/2恒小于r一定會有變化而l只會變成mid1或保持r的值也不會卡住。千萬別把“找左邊界”和“找右邊界”的模板混用如果你在右邊界收縮時用了上取整在某種情況下可能陷入死循環(huán)。最穩(wěn)妥的做法是統(tǒng)一用下取整配合“如果滿足條件把當(dāng)前mid作為新的r”這種寫法。4.3 無解判定的地方還有一種容易漏掉的場景K非常小比如K0。f(0)0f(1)0一直到f(4)0所以K0時應(yīng)該有5個n滿足條件。如果二分區(qū)間設(shè)成[0, 5K]那么[0,0]區(qū)間是可以的第一次二分會在l0停住f(0)0 K再找右邊界得到hi4返回5。只要代碼里沒有特殊把0擋掉這種情況是自然的。但如果你為了圖省事把右邊界設(shè)成5*K1或者更大的額外常數(shù)也能跑只是沒必要。判定“K無解”時陷阱在于直接判斷f(lo) ! K。如果lo已經(jīng)超出了二分上界或者區(qū)間根本沒覆蓋到就會出錯。好在前面定了5K的上界并證明過一定有f(n)K所以不會出現(xiàn)lo越界的問題。這里要注意當(dāng)K很大且f(5K)遠(yuǎn)大于K時左端點一定會在某個f(n)K或者被跳過的地方停下如果跳過了就會返回0這也是正確的。4.4 用手算樣例驗證調(diào)試時建議備一張手動驗算表比盲目試錯快得多。Kf(n)序列情況返回結(jié)果0n0到4f都為051n5到9f都為152n10到14f都為255f(24)4f(25)65被跳過01000000000二分快速定位區(qū)間長度必然為5或0-特別注意K5這一行這是理解“跳檔”的最佳樣例。如果你代碼里的判定方向?qū)懛戳撕苡锌赡茉谶@個樣例上直接返回5而不是0那就說明二分的“”和“”用混了。5. 從793擴(kuò)散二分答案的思路還能用在哪5.1 識別“二分答案可解”的氣質(zhì)做過幾道二分答案題之后我總結(jié)出一個經(jīng)驗一個題能不能用二分答案主要看三點。第一候選答案存在一個有序的取值范圍。這個范圍可以是數(shù)組元素的值域也可以是n本身的值域。第二我們能寫一個判定函數(shù)輸入一個mid快速返回“有多少個候選值滿足某條件”。這個判定函數(shù)往往是O(N)掃一遍有時候是O(logN)。第三目標(biāo)形式是“求滿足某條件的最小/最大值”或者像793題這樣“統(tǒng)計滿足等于某個值的區(qū)間長度”。如果你在題目里看到“第K小”“最大值最小”“最小值最大”“個數(shù)不少于K”這些字眼而且直接做很難先往二分答案上想大概率路是通的。5.2 兩個值得動手的變式順著793的思路有幾道同類型題目很適合練習(xí)某個有序矩陣中求第K小的元素。候選值域就是矩陣最小值和最大值判定函數(shù)統(tǒng)計小于等于mid的元素個數(shù)整體復(fù)雜度O(N log(Max-Min))比直接用優(yōu)先隊列還干凈。乘法表中第K小的數(shù)。同樣先定值域然后對每個候選mid統(tǒng)計“乘法表里有多少個數(shù)小于等于它”這個統(tǒng)計可以按行計算很快。這兩道題我把它們歸類為“二分答案 掃描統(tǒng)計”的組合跟793的關(guān)系是793的判定函數(shù)是數(shù)學(xué)公式那兩題的判定函數(shù)是掃描內(nèi)核完全一致。5.3 “答案只能是0或5”這個殺手級結(jié)論寫到這里忍不住分享一個我剛發(fā)現(xiàn)時覺得很妙的小結(jié)論這道題的答案只會是0或5。為什么觀察序列每次尾零數(shù)量增加都發(fā)生在n恰好是5的倍數(shù)的時候。比如n從4到5f從0跳到1n從24到25f從4跳到6。那么在兩個連續(xù)的5的倍數(shù)之間比如從5到9一共5個連續(xù)nf值都不變。所以同一個尾零數(shù)量K如果有對應(yīng)的n必然是一整段5個連續(xù)整數(shù)。但n25這里f(24)4f(25)6跳過了5于是K5沒有對應(yīng)區(qū)間。這說明一個K要么沒有區(qū)間要么區(qū)間寬度正好是5。所以一旦第一次二分確認(rèn)f(lo) K想都不用想直接可以return 5否則return 0。代碼還能再簡化一半。如果你想把話講清楚證明也很簡單任意區(qū)間[5t, 5t4]內(nèi)的5個整數(shù)其中只有5t這一個數(shù)能貢獻(xiàn)新的5因子剩下4個數(shù)沒有新增5因子因此這5個數(shù)的尾零數(shù)相同。而下一個能改變f值的點必然出現(xiàn)在5(t1)處。平臺的寬度就是5不會有例外。我個人做這類題的習(xí)慣是先把單調(diào)性證明寫出來再想判定函數(shù)的復(fù)雜度最后才動筆寫二分。很多人一上來就套模板結(jié)果邊界寫錯都不知道錯在哪。一次在調(diào)試793的時候我把“找右邊界”的判定從“”改成“”結(jié)果每個無解K都返回5折騰了兩個小時才想起右邊的區(qū)間是開區(qū)間差點把鍵盤拍碎。作為一道“二分答案”的入門題793的代碼量不大但包含的知識密度很高有數(shù)學(xué)推導(dǎo)、有二分邊界、有平臺區(qū)間、有溢出陷阱。把它吃透后面再去啃第K小和第K大的各類變形會發(fā)現(xiàn)套路都長得差不多——先找值域再寫判定函數(shù)最后二分卡邊界。這個思路值得你在任何一道看起來無從下手的K-th問題里第一時間拿出來試一遍。