第一次看到793题的时候我盯着题目看了两分钟第一反应是这题和二分有什么关系阶乘、尾零、K三个词放在一起像是一道背结论的数学题。等我把“二分答案”四个字重新读进脑子才反应过来真正的考点其实不在阶乘怎么算而在“怎么把一个求个数的问题变成一个在值域上二分查找的问题”。这道题的全名很长——阶乘函数后 K 个零刷过在线题库的应该都见过编号是793。题面一句话给定非负整数K问有多少个非负整数n满足 n! 的末尾恰好有 K 个零。很多人一上来就慌了因为n可以巨大K最大能到1e9直接枚举n肯定不行。但这道题恰恰是“二分答案”这一套路里特别经典的入门题练好它对后面啃第K小、第K大类题目帮助很大。1. 先搞懂题目到底在问什么1.1 阶乘尾零是怎么算出来的n! 的末尾有多少个零本质是在问“n! 这个数因子10出现了多少次”。10 2 × 5所以只要数一数n!的质因子分解里有几对2和5尾零就有几个。这里有个关键直觉2的个数永远比5多。1到n之间每两个数才有一个偶数但每五个数才有一个5的倍数理论上前者出现的频率远高于后者。所以尾零的个数完全由因子5的个数决定我们只需要统计1到n中所有数一共贡献了多少个质因子5。怎么数用除法连除累加零的个数 f(n) n/5 n/25 n/125 ...为什么这么加n/5 表示1到n中有多少个5的倍数每个至少贡献一个5但像25、50、75这类数本身有两个5因子第二个5因子被漏掉了所以再加 n/25同理125有三个5因子前两步只统计了两个于是再加 n/125一直加到商为0为止。看两个小例子。10! 3628800末尾2个零。用公式算10/5 210/25 0总数为2正确。25!末尾6个零。公式算25/5 525/25 125/125 0总数为6。手算也能验证25这个数内部就藏了2个5因子所以比f(24)多跳了2。这个公式和实现都不复杂复杂的是“知道有公式之后接下来怎么用它”。1.2 尾零个数序列的真实长相平台、跳跃与单调按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 ...规律很明显f(n)是单调不减的n变大尾零数只会增加或持平不会减少。连续5个数往往共享同一个f值。因为同样尾零数量会一直持续到下一个5的倍数之前平台宽度最多是5。每到5的倍数值会往上跳但有时跳1有时跳更多。比如f(24)4但f(25)6直接跳过5这个值。这里有一层容易忽略的信息既然f(n)会跳档那么K5这种值就找不到任何n对应它。题目问“有多少个n满足f(n)K”答案完全可能是0。这不是特殊情况而是这道题的常态。想通这条序列后面写二分时才能明白为什么要找左边界和右边界。2. 为什么这题要二分“答案”而不是二分“下标”2.1 单调性是二分答案的入场券很多同学一提到二分脑子里只有“给一个有序数组二分查找某个元素”。但二分真正的价值在于只要一个函数在定义域上是单调的我们就可以在值域上做查找而不需要精确知道函数长什么样。f(n)满足非严格单调递增这是一个非常好的性质。现在问题变成了给定K找到所有“通过f(n)映射等于K”的n。我们完全可以拿mid当自变量算f(mid)然后比较f(mid)和K的大小关系。如果f(mid) K说明n取小了左边界往右挪如果f(mid) K说明有可能已经进入“等于K”的区域就往左收缩找更小的可行位置。整个过程不是直接枚举n而是通过二分不断逼近边界。这就像在字典里找一个姓氏的页码范围不用一页页翻先翻中间看首字母比目标大了还是小了然后不断缩小区间。2.2 第K小/第K大问题的通用思考框架把793题挂上“二分答案”的标签是因为它和一类更高频的题目共用同一套思想第K小或第K大。这类题目有个共同特征直接排序所有候选值往往做不到因为候选值的数量可能大到无法枚举但判定“有多少个值小于等于mid”却很容易。经典套路如下确定候选值的范围[lo, hi]这通常是整个数据的最小值和最大值。取mid lo (hi - lo) / 2写一个判定函数 cnt(mid)统计满足条件比如小于等于mid的候选值个数。如果 cnt(mid) K说明第K小的候选值不会比mid更大收缩右边界 hi mid。否则说明第K小候选值至少比mid大收缩左边界 lo mid 1。最终lo停下的位置就是第K小。这其实是“二分答案”的通用骨架。第K大可以换个方向或者数学上转化成第总数-K1小本质一模一样。为什么大家愿意用二分答案因为判定函数往往只要O(N)扫一遍甚至像793题只需要O(logN)而候选值域再大二分也就几十次迭代。这种收益在数据量大的时候极其明显。2.3 793问的不是第K小为什么也归到这里严格来说793题问的不是“第K小是什么”而是“有多少个数的函数值等于K”。但它依然落在“二分答案”这个分类里原因是我们要在n的值域上找到满足 f(n) K 的区间端点。换句话说题目问的是这个区间的长度而区间端点必须靠二分找。你无法用普通二分“找到K然后往两边扩展”的办法因为n可能到4e9量级线性扩展会直接超时。正确做法是第一次二分找“第一个f(n) K”的位置这是左端点。第二次二分找“第一个f(n) K”的位置再减1这是右端点。两个端点一减加1就是答案。这比单纯的“求第K小”多了一点点变化但底层逻辑完全相通利用单调性把问题归结为找边界。3. 二分边界怎么定5K到底够不够3.1 上界选取与证明写二分前先解决一个大问题n的范围到底设到多少题目给出的K最大是1e9。f(n)的渐近形态可以这样估算f(n) n/5 n/25 n/125 ... ≈ n/4这是因为首项1/5后面每项是前一项除以5等比求和极限正好是1/4。所以要让f(n)达到Kn大约需要4K。为了保险二分上界取h 5*K基本足够。之所以说“基本”最好是证明一下对任意正整数K令n 5K那么f(5K) K K/5 K/25 ...这个值一定不小于K。这就说明在区间[0, 5K]内一定能找到f(n)至少为K的位置左端点二分不会跑空。对K0时区间[0,0]也完全没有问题。这里的细节是类型。K本身是int但5*K当K1e9时达到5e9早就超出32位int的范围。所以上界必须用long long存不然大概率会出现负数边界二分直接崩掉。很多第一次写这题的人就是栽在这一步。3.2 两次二分的写法第一次二分找左边界l 0 r 5 * K while l r: mid (l r) / 2 if trailingZeroes(mid) K: r mid else: l mid 1这个模板的语义是不断压低右边界找到第一个满足“尾零数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它找的是第一个“尾零数大于K”的n找到后减1就是最后一个“尾零数等于K”的位置。有人会问为什么第一个找“”第二个找“”因为我们要的区间左闭右开。第二个位置本身不属于答案属于右边第一个超出区间的点。两次二分用的是同一个值域判定条件差一个等号这就是区间端点二分的标准姿势。3.3 完整C实现下面给一份可以直接跑通的代码注释写在关键位置方便对照理解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; // 如果这个位置算出来的尾零数不等于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; } };这里我做了一个小优化如果第一次二分结束lo位置的f(lo)不等于K说明K这个值根本不存在直接返回0没必要再跑第二次二分。这个优化虽然小但能让无解分支的速度快一倍。4. 常见坑点与调试实录4.1 溢出不是小问题刚开始写这题的某同学第一次提交用int存二分上界K传1e9的时候5*K直接变成了负的二分区间完全错乱。当时他把trailingZeroes函数也写成int型n/5累加在大数下溢出结果跑了几个样例全错。这是个特别容易忽略的点只要N的范围允许到5e9那么所有跟n打交道的位置都要用long long。判定函数的参数、返回值和临时变量全部要带类型。我见过不少人只把right改成long long但trailingZeroes里还在用int接收参数照样错。4.2 死循环与mid取整二分模板里有人习惯写mid (l r 1) / 2有人习惯写mid (l r) / 2。这两种对应不同的边界更新习惯。在这个题里两个二分都是“左边界向右侧收缩”的模式用下取整不会死循环。因为当l r时mid (lr)/2恒小于r一定会有变化而l只会变成mid1或保持r的值也不会卡住。千万别把“找左边界”和“找右边界”的模板混用如果你在右边界收缩时用了上取整在某种情况下可能陷入死循环。最稳妥的做法是统一用下取整配合“如果满足条件把当前mid作为新的r”这种写法。4.3 无解判定的地方还有一种容易漏掉的场景K非常小比如K0。f(0)0f(1)0一直到f(4)0所以K0时应该有5个n满足条件。如果二分区间设成[0, 5K]那么[0,0]区间是可以的第一次二分会在l0停住f(0)0 K再找右边界得到hi4返回5。只要代码里没有特殊把0挡掉这种情况是自然的。但如果你为了图省事把右边界设成5*K1或者更大的额外常数也能跑只是没必要。判定“K无解”时陷阱在于直接判断f(lo) ! K。如果lo已经超出了二分上界或者区间根本没覆盖到就会出错。好在前面定了5K的上界并证明过一定有f(n)K所以不会出现lo越界的问题。这里要注意当K很大且f(5K)远大于K时左端点一定会在某个f(n)K或者被跳过的地方停下如果跳过了就会返回0这也是正确的。4.4 用手算样例验证调试时建议备一张手动验算表比盲目试错快得多。Kf(n)序列情况返回结果0n0到4f都为051n5到9f都为152n10到14f都为255f(24)4f(25)65被跳过01000000000二分快速定位区间长度必然为5或0-特别注意K5这一行这是理解“跳档”的最佳样例。如果你代码里的判定方向写反了很有可能在这个样例上直接返回5而不是0那就说明二分的“”和“”用混了。5. 从793扩散二分答案的思路还能用在哪5.1 识别“二分答案可解”的气质做过几道二分答案题之后我总结出一个经验一个题能不能用二分答案主要看三点。第一候选答案存在一个有序的取值范围。这个范围可以是数组元素的值域也可以是n本身的值域。第二我们能写一个判定函数输入一个mid快速返回“有多少个候选值满足某条件”。这个判定函数往往是O(N)扫一遍有时候是O(logN)。第三目标形式是“求满足某条件的最小/最大值”或者像793题这样“统计满足等于某个值的区间长度”。如果你在题目里看到“第K小”“最大值最小”“最小值最大”“个数不少于K”这些字眼而且直接做很难先往二分答案上想大概率路是通的。5.2 两个值得动手的变式顺着793的思路有几道同类型题目很适合练习某个有序矩阵中求第K小的元素。候选值域就是矩阵最小值和最大值判定函数统计小于等于mid的元素个数整体复杂度O(N log(Max-Min))比直接用优先队列还干净。乘法表中第K小的数。同样先定值域然后对每个候选mid统计“乘法表里有多少个数小于等于它”这个统计可以按行计算很快。这两道题我把它们归类为“二分答案 扫描统计”的组合跟793的关系是793的判定函数是数学公式那两题的判定函数是扫描内核完全一致。5.3 “答案只能是0或5”这个杀手级结论写到这里忍不住分享一个我刚发现时觉得很妙的小结论这道题的答案只会是0或5。为什么观察序列每次尾零数量增加都发生在n恰好是5的倍数的时候。比如n从4到5f从0跳到1n从24到25f从4跳到6。那么在两个连续的5的倍数之间比如从5到9一共5个连续nf值都不变。所以同一个尾零数量K如果有对应的n必然是一整段5个连续整数。但n25这里f(24)4f(25)6跳过了5于是K5没有对应区间。这说明一个K要么没有区间要么区间宽度正好是5。所以一旦第一次二分确认f(lo) K想都不用想直接可以return 5否则return 0。代码还能再简化一半。如果你想把话讲清楚证明也很简单任意区间[5t, 5t4]内的5个整数其中只有5t这一个数能贡献新的5因子剩下4个数没有新增5因子因此这5个数的尾零数相同。而下一个能改变f值的点必然出现在5(t1)处。平台的宽度就是5不会有例外。我个人做这类题的习惯是先把单调性证明写出来再想判定函数的复杂度最后才动笔写二分。很多人一上来就套模板结果边界写错都不知道错在哪。一次在调试793的时候我把“找右边界”的判定从“”改成“”结果每个无解K都返回5折腾了两个小时才想起右边的区间是开区间差点把键盘拍碎。作为一道“二分答案”的入门题793的代码量不大但包含的知识密度很高有数学推导、有二分边界、有平台区间、有溢出陷阱。把它吃透后面再去啃第K小和第K大的各类变形会发现套路都长得差不多——先找值域再写判定函数最后二分卡边界。这个思路值得你在任何一道看起来无从下手的K-th问题里第一时间拿出来试一遍。
