整理二分答案题单的时候，我在 793 这道题上卡了两次：第一次是没读懂它到底让我求什么，第二次是搞不清k=5这种“落空”的情况该怎么收敛。这道题表面挂着“阶乘函数后 K 个零”的数学外壳，内核其实是典型的二分答案问题，而且和“第K小/第K大”那个反直觉的分治思维非常贴合——你手上没有数组，只有一个可以随算随取的函数f(x)，你要根据函数值反推出自变量的区间。这篇文章就把 793 从读题、数学推导、二分区间的设计、代码落地到同类题的迁移完整讲一遍，适合正在刷二分查找/二分答案专题的人，或者被这道题卡住准备直接抄作业的朋友。
1. 题目真正要的东西，和标题给人的第一印象
1.1 先把这个函数读明白
题目定义f(x) = x! 尾零的个数，输入一个整数k，问有多少个非负整数x满足f(x) == k。
很多人第一次读这题都会产生一个惯性误解：x是输入，k是输出，那就枚举x呗。可题目反过来了——k是给定的函数值，要你统计有多少个自变量能取到这个值。举个例子，k = 0的时候答案不是 0，也不是无穷大，而是 5。因为0!, 1!, 2!, 3!, 4!这 5 个阶乘的末尾都没有 0，f(0) = f(1) = f(2) = f(3) = f(4) = 0，到了5!才出现第一个尾零。
这个“统计个数”的设定很容易让人往哈希表、枚举之类的地方想。但如果k给到接近10^9，对应的x大概在4 * 10^9附近，枚举是不可能枚举完的。也就是说，题目真正考查的并不是“你怎么暴力算出阶乘尾零”，而是“你能不能看出这是一个单调函数上的区间查询问题”。
1.2 别碰阶乘，别碰枚举
先给一个量级概念：f(x) = floor(x/5) + floor(x/25) + floor(x/125) + ...，这个式子后面会详细推导。它有一个很粗略的等价关系：
f(x) ≈ x/4
因为1/5 + 1/25 + 1/125 + ... = (1/5) / (1 - 1/5) = 1/4。也就是说x大约是k的 4 倍。当k = 10^9时，x至少是4 * 10^9，早就超出了 32 位整数的范围，也远远超过任何暴力枚举的能承受的规模。阶乘本身更不用算，哪怕是20!就已经有 19 位数字了，直接构造阶乘再数零，在k很大的时候连理论可能性都没有。
所以这道题必然走数论捷径：尾零个数只取决于阶乘分解质因数后2和5的指数，而5的指数是稀缺资源。这一点下一节专门讲。
1.3 题单里的定位：它为什么挂在“二分答案”下面
标题前缀是“D.二分查找－二分答案－第K小/第K大”。这个分类其实泄露了正解方向。经典的二分查找是在一个有序数组里找某个值的位置，而二分答案是在一个“值域”上做二分，每次二分出一个猜测值mid，再用一个判定函数判断mid是否满足条件，最后把搜索范围收敛到答案。
793 的特点就是：你没有一个现成的数组，只有一个可以随时计算的函数f(x)，它是单调不降的。单调不降的函数就相当于一个“无限长的有序数组”，你可以在自变量x的值域上二分，去定位某个函数值出现的位置。标题里“第K小/第K大”那一串词，指的是这一类题的最终形态——给定排名k，在二分中通过比较cnt(mid)和k来逼近答案。793 也是这个套路，只是它最后不是返回“第K小的值”，而是返回“函数值等于 k 的自变量有多少个”。
2. 核心观察：尾零个数是五因子的阶梯
2.1 10 的因子匹配，谁稀缺看谁
一个十进制数的末尾零，本质上是它被10整除的次数。10 = 2 × 5，所以一个数末尾零的数量等于它的质因数分解中2的指数和5的指数取最小值：min(v2, v5)。
考虑x! = 1 × 2 × 3 × ... × x，把所有数分别拆成2的幂和5的幂，2的因子出现得非常频繁：每 2 个数就有一个偶数，每 4 个数就有一个能被 4 整除。而5的因子每 5 个数才出现一次。显然在整个阶乘里v2 >= v5，所以：
f(x) = v5(x! )
末尾零的个数，只看阶乘里“5 这个质因子一共出现了多少次”。这个结论太关键了，它把“数 10”的问题变成了“数 5”的问题。
2.2 勒让德公式：数 5 的因子怎么数
现在要数x!里有多少个质因子 5。做法很简单：先数 1 到x之间有多少个 5 的倍数，每个至少贡献一个 5；再数有多少个 25 的倍数，每个额外多贡献一个 5；再数有多少个 125 的倍数，每个再额外贡献一个 5……以此类推。写成公式就是：
f(x) = floor(x/5) + floor(x/25) + floor(x/125) + ...
这里要防止一个常见误解：有人觉得floor(x/25)已经包含在floor(x/5)里了，为什么还要再加一遍？确实，25的倍数同时也是5的倍数，在floor(x/5)里已经被算过一次，但一个数如果含有两个 5 因子，它需要被算两次。floor(x/25)补充的就是“第二层 5 因子”。同理，floor(x/125)补充第三层。所以这个式子是累加而不是嵌套。
试算一下：24!里 5 的倍数有 4 个（5、10、15、20），25 的倍数有 0 个，所以f(24) = 4。而25!里 5 的倍数有 5 个，25 的倍数有 1 个，所以f(25) = 5 + 1 = 6。你看，从 24 到 25，函数值从 4 直接跳到了 6——跳过了 5。这个跳跃在后面的算法设计里是决定性的。
2.3 阶梯形状带来的两个推论
有了这个计数公式，f(x)的图像就清楚了：它是一条单调不降的台阶线。x每增加 1，函数值要么不变，要么在遇到新的 5 的倍数时往上跳一步，甚至可能跳好几级（比如从 124 到 125，floor(125/5)=25、floor(125/25)=5、floor(125/125)=1，一下子多出 6 个 5 因子，但我这个例子已经跨越了一个大台阶）。
这个阶梯形状直接带出两个推论：
- 满足
f(x) = k的所有x，一定构成一个连续整数区间。因为函数单调不降，函数值从< k变成== k，再变成> k，中间不可能先等于再不等再等于。 - 某些
k会被完全跳过，比如k = 5。这时候答案是 0。
所以这道题从“统计个数”变成了“找到这个连续区间的左右端点，再判断区间是否存在”。二分答案的思路就顺理成章了。
3. 二分的正确姿势：用两个端点包围答案
3.1 定义一个“首个大于等于”函数
既然答案是连续区间，那最关键的操作是：给定一个目标值k，找到最小的x使得f(x) >= k。我把它记作L(k)：
L(k) = min { x | f(x) >= k }
因为f(x)单调不降，f(x) >= k这个条件对x来说具有“一旦成立就不回头”的性质。这正好是二分查找里的lower_bound语义。你可以把它理解成：在一条无限长的台阶上，找到第k级台阶踩实的第一块砖。
3.2 用 L(k) 和 L(k+1) 做差，量出台阶宽度
所有的答案都在[L(k), L(k+1) - 1]这个区间里。为什么？
先看左端点：L(k)是第一个让f(x) >= k的位置，所以从这个位置开始，函数值至少是k。
再看右端点：L(k+1)是第一个让f(x) >= k+1的位置。那么所有小于L(k+1)的x，都满足f(x) < k+1。因为f(x)的取值都是整数，f(x) < k+1就等价于f(x) <= k。
两边一夹，对于任意x ∈ [L(k), L(k+1) - 1]，同时有f(x) >= k和f(x) <= k，所以f(x) = k。反之，区间外的x要么函数值小于k，要么已经大于等于k+1，都不可能是答案。因此答案数量正好是：
answer = L(k+1) - L(k)
但这里有一个前提：L(k)处的函数值真的等于k。如果k被人为跳过去了，比如k=5，那么L(5)=25，但f(25)=6。此时[L(5), L(6)-1]是个空区间，因为L(5)=L(6)=25，做差得到 0。所以正确的处理是分两步：
- 二分得到
L(k)。 - 检查
f(L(k)) == k。如果不等，说明k落在空洞里，直接返回 0；如果相等，再二分得到L(k+1)，返回L(k+1) - L(k)。
很多人写这题的时候只在最后返回一个差值，没做验证，结果k=5这种数据会错得莫名其妙。验证这一步不是防御性代码，是空洞检测本身。
3.3 二分上下界的数学保证
二分需要一个初始右边界hi。这里不能随手写10^18——虽然不会超时，但不够精致。更好的选择是：
hi = 5 * (k + 1) + 5
为什么够用？因为f(hi) >= floor(hi / 5)，只要floor(hi / 5) >= k + 1，就一定满足f(hi) >= k + 1。取hi = 5 * (k + 1) + 5时，floor(hi / 5) = k + 2，所以L(k)和L(k+1)都在[0, hi]范围内，二分不会漏。
从这里还能看出long long的必要性：k最大取到10^9时，hi大约是5 * 10^9 + 5，已经超出 32 位int的范围。如果用int，边界直接溢出，二分会跑到一个完全错误的区间里。这个坑我在第五部分会专门说。
现在整个算法骨架已经出来了：
left = lowerBound(k) if f(left) != k: return 0 right = lowerBound(k + 1) return right - left核心工作只剩一个lowerBound的实现。
4. 代码落地：二分模板的三处细节
4.1 完整实现
def zeros(x: int) -> int: """计算 x! 末尾零的个数，等于 x! 中质因子 5 的指数""" cnt = 0 while x: x //= 5 cnt += x return cnt def lower_bound(target: int) -> int: """返回最小的 x，使得 zeros(x) >= target""" lo, hi = 0, 5 * target + 5 while lo < hi: mid = (lo + hi) // 2 if zeros(mid) >= target: hi = mid else: lo = mid + 1 return lo def preimageSizeFZF(k: int) -> int: left = lower_bound(k) if zeros(left) != k: return 0 right = lower_bound(k + 1) return right - leftzeros(x)的实现就是勒让德公式的循环版。注意while x和x //= 5的顺序：先除再加，保证第一项是x/5而不是x。如果把顺序写反，第一轮就会把x本体的贡献误算进去。
4.2 二分模板细节，为什么这样写
lower_bound用的是标准的“左闭右开语义下的最小可行值”模板：
- 判定条件是
zeros(mid) >= target，不是==，更不是>。因为我们要找的是“第一个满足 >=”的位置，不是“某个刚好等于”的位置。 - 满足条件时收缩右边界
hi = mid，不满足时收缩左边界lo = mid + 1，这样循环结束时lo就是第一个可行位置。 hi初始化为5 * target + 5，保证初始区间一定包含答案；lo从 0 开始，因为zeros(0) = 0，当target = 0时答案恰好是 0。
有一个容易写错的地方是mid = (lo + hi) // 2与lo = mid + 1的组合。如果你不小心把hi的收缩写成hi = mid - 1，在lo == hi时就会出现死循环。这类二分边界问题的通用解法就是记住：区间始终包含所有未排除的候选值，收缩时必须从候选里去掉 mid，只有不再把 mid 当成候选时才用mid + 1或mid - 1。上面这个模板我已经在好几个二分答案题里复用过了，稳定。
4.3 用手算验证核心逻辑
拿几个k值走一遍流程：
| k | lower_bound(k) | zeros(left) | lower_bound(k+1) | 结果 |
|---|---|---|---|---|
| 0 | 0 | 0 | 5 | 5 |
| 1 | 5 | 1 | 10 | 5 |
| 5 | 25 | 6 | 25 | 0 |
| 6 | 25 | 6 | 30 | 5 |
| 10 | 45 | 10 | 50 | 5 |
k=5是最容易出错的：f(24)=4，f(25)=6，5 被跳过了。二分找到的left=25，但验证时发现zeros(25)=6 != 5，于是返回 0。这正对应前面说的空洞检测。
k=10可以手算验证：f(44) = 8 + 1 = 9，f(45) = 9 + 1 = 10，f(49) = 9 + 1 = 10，f(50) = 10 + 2 = 12。所以满足f(x)=10的x是 45 到 49，一共 5 个。算法里lower_bound(10)=45，lower_bound(11)=50，差值是 5，正确。
5. 几个几乎必踩的坑
5.1 k=0 不是无解，也不是无限解
很多人一看到k=0就觉得“既然一直有阶乘，尾零为 0 的 x 应该很多吧”，这是错的。f(x)是单调不降的，一旦出现第一个尾零就再也不会回到 0。满足f(x)=0的只有x=0,1,2,3,4这 5 个。这个边界用上面的算法跑一遍自然得到 5，不需要特判，但前提是zeros函数能正确处理x=0：while x循环在x=0时压根不进入，返回 0，这就是f(0)=0的来源。
5.2 空洞判断必须放在求右端点之前
有一种错误的写法是这样的：先把left = lower_bound(k)算出来，再算right = lower_bound(k+1)，最后判断if left == right: return 0。这个判断本身没错，但如果你把验证放在最后，碰到k在空洞里的情况，你白白多跑了一次二分，而且代码的意图很不清晰。先验证zeros(left) == k，不相等就直接返回 0，语义上就是“这个台阶被我跨过去了，空洞确定存在”，比用left == right暗示要直观得多。
5.3 int 溢出是一个隐蔽的炸弹
k最大是10^9，hi = 5 * target + 5大约5 * 10^9。在 C++ 或 Java 里如果target是int，5 * target是用int运算的，直接溢出成负值，二分区间直接崩掉。解决办法是写5LL * target或者把整个边界都提升为long long。Python 没有这个问题，但如果你在面试里写的是 C++，这几乎是必现错误。
5.4 zeros 循环的迭代次数别高估
zeros(x)的循环次数大约是log_5(x)。当x接近5 * 10^9时，log_5(x) ≈ log_5(5e9) ≈ 13.9，也就是最多 14 次除法。而二分本身大约需要log_2(5e9) ≈ 32次迭代。总计算量在几百次基本运算的级别，所以整个解法的时间复杂度是O(log k * log_5 k)，空间O(1)。我第一次看这个复杂度的时候也愣了一下——看起来是两个 log 相乘，实际上常数极小，跑完一个大数据测试只需要微秒级。
6. 从 793 扩散：一类“二分答案 + 计数判定”的题
6.1 通法三段式
刷完 793 之后我最大的收获，是把“第K小/第K大”这类题总结成了一个三步套路：
- 确定二分对象：对答案的数值范围进行二分，而不是对某个现成数组的下标二分。
- 设计判定函数：给定一个猜测值
mid，计算有多少个元素/方案满足<= mid，得到一个计数cnt。 - 比较收缩：如果
cnt >= k，说明答案太大或正好，收缩右边界；否则收缩左边界。最终收敛的位置就是答案。
793 的独特之处在于，它把第二步的“cnt >= k”改成了“zeros(mid) >= k”，并且最后输出的是一个区间宽度，而不是单一值。这说明套路不是死板的模板，你需要理解它在做什么：二分答案的本质是“用判定函数模拟有序性”。
6.2 同套路题目对照表
刷的时候可以把下面这些题放在一起看，它们的骨架几乎一样，只是判定函数不同：
| 题目特征 | 二分对象 | 判定函数 | 返回内容 |
|---|---|---|---|
| 有序矩阵第 K 小 | 矩阵元素值 | 统计矩阵中<= v的元素个数 | 第 K 小的元素 |
| 找出第 K 小的数对距离 | 距离值 | 双指针统计差<= v的数对数量 | 第 K 小距离 |
| 丑数 III | 数值范围 | 容斥原理统计区间内丑数个数 | 第 K 个丑数 |
| 第 K 小乘积 | 乘积值 | 双指针统计乘积<= v的组合数量 | 第 K 小乘积 |
| 793 阶乘函数后 K 个零 | 自变量 x | 用zeros(x) >= k定位台阶端点 | 函数值等于 k 的 x 数量 |
它们的共同点是：答案的数值范围很大，不能枚举，但判定函数能快速统计。你只要把判定函数写对，二分部分基本可以复制粘贴。
6.3 793 的特殊结论：什么时候返回 0，什么时候返回宽度
普通“第K小”题目不存在“空洞”的概念，因为统计元素个数是连续的，每个排名都有对应的元素。但 793 的单调函数不是严格递增的，它是台阶状的，于是会出现某些函数值被跳过的现象。这个“空洞”就是k不落在任何台阶上的情况。
判断方法已经写进算法了：zeros(L(k)) != k。如果相等，说明k确实是一个台阶的值，那么L(k+1) - L(k)就是这个台阶上所有整数的数量。顺带提一句，台阶宽度大多数情况下是 5，因为连续 5 个整数里最多包含一个 5 的倍数。但当跨越 25、125 这些更高次幂时，台阶会被跳过，于是某个函数值对应的宽度不再是 5，而是变成了 0 或者别的长度。
最后分享一个实操体会：我后来再遇到“函数值回查自变量区间”的题，都会先在草稿纸上画一条楼梯线，把L(k)和L(k+1)标出来。只要这条线画明白了，代码基本就是照抄二分边界。793 这道题最值得练的不是那个数论公式，而是“把一个单调函数的台阶宽度拆成两个 lower_bound 做差”的思维方式。这个思维在以后处理连续区间计数问题时，比背任何模板都管用。
