二分答案经典题：阶乘函数后K个零的解法与边界陷阱

第一次看到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 = 2，10/25 = 0，总数为2，正确。

25!末尾6个零。公式算：25/5 = 5，25/25 = 1，25/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 ...

规律很明显：

1. f(n)是单调不减的，n变大，尾零数只会增加或持平，不会减少。
2. 连续5个数往往共享同一个f值。因为同样尾零数量会一直持续到下一个5的倍数之前，平台宽度最多是5。
3. 每到5的倍数，值会往上跳，但有时跳1，有时跳更多。比如f(24)=4，但f(25)=6，直接跳过5这个值。

这里有一层容易忽略的信息：既然f(n)会跳档，那么K=5这种值就找不到任何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大可以换个方向，或者数学上转化成第（总数-K+1）小，本质一模一样。

为什么大家愿意用二分答案？因为判定函数往往只要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)达到K，n大约需要4K。为了保险，二分上界取h = 5*K基本足够。

之所以说“基本”，最好是证明一下：对任意正整数K，令n = 5K，那么f(5K) = K + K/5 + K/25 + ...，这个值一定不小于K。这就说明在区间[0, 5K]内，一定能找到f(n)至少为K的位置，左端点二分不会跑空。对K=0时，区间[0,0]也完全没有问题。

这里的细节是类型。K本身是int，但5*K当K=1e9时达到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*K，K最大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 = (l+r)/2恒小于r，一定会有变化；而l只会变成mid+1或保持r的值，也不会卡住。

千万别把“找左边界”和“找右边界”的模板混用：如果你在右边界收缩时用了上取整，在某种情况下可能陷入死循环。最稳妥的做法是统一用下取整，配合“如果满足条件，把当前mid作为新的r”这种写法。

4.3 无解判定的地方

还有一种容易漏掉的场景：K非常小，比如K=0。

f(0)=0，f(1)=0，一直到f(4)=0，所以K=0时应该有5个n满足条件。如果二分区间设成[0, 5K]，那么[0,0]区间是可以的，第一次二分会在l=0停住，f(0)=0 == K，再找右边界得到hi=4，返回5。只要代码里没有特殊把0挡掉，这种情况是自然的。但如果你为了图省事，把右边界设成5*K+1或者更大的额外常数，也能跑，只是没必要。

判定“K无解”时，陷阱在于：直接判断f(lo) != K。如果lo已经超出了二分上界，或者区间根本没覆盖到，就会出错。好在前面定了5K的上界，并证明过一定有f(n)>=K，所以不会出现lo越界的问题。这里要注意：当K很大且f(5K)远大于K时，左端点一定会在某个f(n)==K或者被跳过的地方停下；如果跳过了，就会返回0，这也是正确的。

4.4 用手算样例验证

调试时建议备一张手动验算表，比盲目试错快得多。

特别注意K=5这一行，这是理解“跳档”的最佳样例。如果你代码里的判定方向写反了，很有可能在这个样例上直接返回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到5，f从0跳到1；n从24到25，f从4跳到6。那么在两个连续的5的倍数之间，比如从5到9，一共5个连续n，f值都不变。所以同一个尾零数量K，如果有对应的n，必然是一整段5个连续整数。

但n=25这里，f(24)=4，f(25)=6，跳过了5，于是K=5没有对应区间。这说明一个K要么没有区间，要么区间宽度正好是5。

所以一旦第一次二分确认f(lo) == K，想都不用想，直接可以return 5；否则return 0。代码还能再简化一半。

如果你想把话讲清楚，证明也很简单：任意区间[5t, 5t+4]内的5个整数，其中只有5t这一个数能贡献新的5因子，剩下4个数没有新增5因子，因此这5个数的尾零数相同。而下一个能改变f值的点，必然出现在5(t+1)处。平台的宽度就是5，不会有例外。

我个人做这类题的习惯是：先把单调性证明写出来，再想判定函数的复杂度，最后才动笔写二分。很多人一上来就套模板，结果边界写错都不知道错在哪。一次在调试793的时候，我把“找右边界”的判定从“>”改成“>=”，结果每个无解K都返回5，折腾了两个小时才想起右边的区间是开区间，差点把键盘拍碎。

作为一道“二分答案”的入门题，793的代码量不大，但包含的知识密度很高：有数学推导、有二分边界、有平台区间、有溢出陷阱。把它吃透，后面再去啃第K小和第K大的各类变形，会发现套路都长得差不多——先找值域，再写判定函数，最后二分卡边界。这个思路，值得你在任何一道看起来无从下手的K-th问题里，第一时间拿出来试一遍。