LeetCode 793. 阶乘函数后 K 个零
目录
题目描述
题意分析
题目目标：定义 $f(x)$ 为 $x!$ 末尾零的个数，给定 $k$，问有多少个非负整数 $x$ 满足 $f(x) = k$。
核心约束：$k$ 最大到 $10^9$，而使 $f(x) = k$ 的 $x$ 大约在 $5k$ 量级，也就是 $5 \times 10^9$——远超 32 位整数范围，所有涉及上界和中点的运算都必须用 64 位。同时题目问的是「有多少个 $x$」而不是「$x$ 是多少」，这提示答案可能有固定结构而不需要真的枚举。
边界处理：$k$ 可以为 0，此时 $x \in {0, 1, 2, 3, 4}$ 都满足，答案是 5 而不是 4；$f$ 不是满射，很多 $k$ 根本没有原像（比如 $k = 5$），此时答案是 0；$x = 0$ 时 $0! = 1$，$f(0) = 0$，不能漏。
实现取舍：直接枚举 $x$ 从 0 试到 $5k$ 是 $O(k)$，$10^9$ 会超时。$f$ 单调不减这一点让二分成为必然选择，剩下的取舍只是「二分找区间两端」还是「先判存在性再乘 5」。前者更通用，也更容易讲清楚。
解法：二分边界（找区间长度）
核心思路
先把 $f$ 算清楚。末尾零的个数等于 $x!$ 中因子 10 的个数，而 10 = 2 × 5，$x!$ 里因子 2 远多于因子 5，所以零的个数就是因子 5 的个数：$f(x) = \lfloor x/5 \rfloor + \lfloor x/25 \rfloor + \lfloor x/125 \rfloor + \dots$。这就是「172. 阶乘后的零」的结论，本题把它当作已知工具。
暴力就是从 $x = 0$ 开始逐个算 $f(x)$，统计等于 $k$ 的个数。瓶颈很清楚：$x$ 要试到 $5 \times 10^9$，即使每次 $f$ 只要 $O(\log_5 x)$，总量也是 $10^{10}$ 级别。
关键观察一：$f$ 单调不减。$x$ 增大时求和式里每一项都不会变小，所以 ${x : f(x) = k}$ 一定是一段连续区间（可能为空）。既然是连续区间，就不必逐个数，只要求出左右两端即可——这正是二分的用武之地。
关键观察二：这个区间要么为空，要么恰好长度为 5。因为 $f(x+1) - f(x)$ 等于 $x+1$ 中因子 5 的个数：当 $x+1$ 不是 5 的倍数时增量为 0，当 $x+1$ 是 5 的倍数时增量至少为 1。也就是说 $f$ 只在 5 的倍数处「跳台阶」，两个相邻台阶之间恰好平了 5 个整数。所以答案非 0 即 5。不过这条性质只用来做直觉验证，代码里并不依赖它——直接用右端减左端更稳。
于是把问题转成两个标准的二分模板。定义
lowerBound(k)= 最小的 $x$ 使countZero(x) >= k，upperBound(k)= 最小的 $x$ 使countZero(x) > k。区间 $[\text{lowerBound}(k), \text{upperBound}(k))$ 恰好就是所有 $f(x) = k$ 的 $x$，答案即两者之差。这个写法的好处是：无解时两个边界会重合，差自动为 0，不需要额外的存在性判断。
不变量写明白：二分维护半开区间 $[lo, hi)$，循环中始终保证「答案落在 $[lo, hi]$ 内」，条件成立时收缩右界
hi = mid（mid本身可能是答案，不能丢），不成立时收缩左界lo = mid + 1（mid已被排除）。搜索上界取 $5(k+1) + 5$，因为 $f(5(k+1)) \ge k+1 > k$，两个边界都必然落在这个范围内。
解题步骤
第一步：实现
countZero(x)，循环x /= 5并累加商。 为什么这样写等价于求和式：第一次x /= 5得到 $\lfloor x/5 \rfloor$，第二次得到 $\lfloor x/25 \rfloor$（整除的嵌套等于一次性除以 25），依此类推，累加即得 $f(x)$，循环次数是 $\log_5 x$。为什么参数和返回值都用 64 位：$x$ 会达到 $5 \times 10^9$，返回值也可能超过 $10^9$。
第二步：确定二分上界
hi = 5 * (k + 1) + 5。 为什么够大：$f(5m) \ge m$ 恒成立，取 $m = k+1$ 得 $f(5(k+1)) \ge k+1 > k$，所以「最小的使 $f > k$ 的 $x$」不会超过 $5(k+1)$；再留 5 的余量纯粹是保险。为什么要写成5L * (k + 1)：k是int，$k = 10^9$ 时5 * (k+1)在int下溢出成负数。
第三步：
lowerBound(k)用「条件为countZero(mid) >= k」的二分。 为什么用>=：我们要的是第一个「零的个数不少于 $k$」的位置，它就是 $f(x) = k$ 区间的左端（若 $k$ 有原像）。为什么循环条件是lo < hi而不是lo <= hi：半开区间语义下lo == hi就意味着区间收缩到一点，此时答案已确定。
第四步：
upperBound(k)用「条件为countZero(mid) > k」的同一套模板。 为什么只改一个符号：两个函数搜索的是同一个单调布尔序列上不同的分界点，模板骨架必须完全一致，否则两个边界的语义会错位。
第五步：返回
upperBound(k) - lowerBound(k)。 为什么这个差自动处理了无解：若不存在 $f(x) = k$，说明 $f$ 在某处直接从小于 $k$ 跳到大于 $k$，那么「第一个 $\ge k$」和「第一个 $> k$」是同一个位置，差为 0。
第六步：
mid用lo + (hi - lo) / 2而不是(lo + hi) / 2。 为什么：即便在long下 $10^{10}$ 量级的相加也不会溢出，但保持这个写法是肌肉记忆，换到边界更大的题上直接受益。
以
k = 3走一遍。上界hi = 5 * 4 + 5 = 25。
先跑
lowerBound(3)，条件是countZero(mid) >= 3。区间 $[0, 25)$：mid = 12，countZero(12) = 12/5 = 2，再除得 0，共 2，不满足 $\ge 3$，说明 12 及其左边全部出局，lo = 13。区间 $[13, 25)$：mid = 19，countZero(19) = 3，满足，hi = 19（19 本身可能就是答案，所以不能写hi = 18）。区间 $[13, 19)$：mid = 16，countZero(16) = 3，满足，hi = 16。区间 $[13, 16)$：mid = 14，countZero(14) = 2，不满足，lo = 15。区间 $[15, 16)$：mid = 15，countZero(15) = 3，满足，hi = 15。此时lo == hi == 15，返回 15。
再跑
upperBound(3)，条件换成countZero(mid) > 3。区间 $[0, 25)$：mid = 12，countZero = 2，不满足，lo = 13。区间 $[13, 25)$：mid = 19，countZero = 3，注意 3 不大于 3，不满足，lo = 20——这一步就是两个二分唯一分道扬镳的地方。区间 $[20, 25)$：mid = 22，countZero(22) = 4，满足，hi = 22。区间 $[20, 22)$：mid = 21，countZero(21) = 4，满足，hi = 21。区间 $[20, 21)$：mid = 20，countZero(20) = 4，满足，hi = 20。lo == hi == 20，返回 20。
答案 $20 - 15 = 5$。验证一下：$f(15) = f(16) = f(17) = f(18) = f(19) = 3$，$f(20) = 4$，确实是 15、16、17、18、19 这 5 个数，与「非 0 即 5」的结论吻合。
再看无解的
k = 5：lowerBound(5)会停在 25（$f(24) = 4$，$f(25) = 6$），upperBound(5)找第一个 $f > 5$ 的位置，同样是 25。差为 0，正确地反映了「$f(x)$ 从 4 直接跳到 6，跳过了 5」。
代码实现
class Solution {
public int preimageSizeFZF(int k) {
long left = lowerBound(k);
long right = upperBound(k);
return (int) (right - left);
}
private long lowerBound(int k) {
long lo = 0;
long hi = 5L * (k + 1) + 5;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (countZero(mid) >= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
private long upperBound(int k) {
long lo = 0;
long hi = 5L * (k + 1) + 5;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (countZero(mid) > k) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
private long countZero(long x) {
long count = 0;
while (x > 0) {
x /= 5;
count += x;
}
return count;
}
}
func preimageSizeFZF(k int) int {
left := lowerBound(k)
right := upperBound(k)
return int(right - left)
}
func lowerBound(k int) int64 {
var lo int64 = 0
var hi int64 = 5*int64(k+1) + 5
for lo < hi {
mid := lo + (hi-lo)/2
if countZero(mid) >= int64(k) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
func upperBound(k int) int64 {
var lo int64 = 0
var hi int64 = 5*int64(k+1) + 5
for lo < hi {
mid := lo + (hi-lo)/2
if countZero(mid) > int64(k) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
func countZero(x int64) int64 {
var count int64 = 0
for x > 0 {
x /= 5
count += x
}
return count
}
复杂度分析
- 时间复杂度：$O(\log^2 k)$。凭什么：两次二分各需 $O(\log(5k))$ 轮，每轮调用一次
countZero，而countZero内部每次把 $x$ 除以 5，循环 $O(\log_5 x)$ 次，两者相乘即为 $\log$ 的平方；$k \le 10^9$ 时大约是 $33 \times 15 \times 2$ 次基本运算，可以忽略不计。- 空间复杂度：$O(1)$。凭什么：全程只有
lo、hi、mid、count几个 64 位标量，没有递归也没有数组。
关键点总结
- 答案是「计数」而不是「求值」时，先判断解集是否连续。 单调函数的等值集必为区间，于是计数问题化为两次边界二分，这是本题最核心的一次转化。
lowerBound与upperBound用同一套模板、只改比较符号。 保持骨架一致，两个边界的语义才对得齐；把其中一个改成lo <= hi或hi = mid - 1就会错位。- 用「右端减左端」代替「先判存在再算长度」。 差值天然处理了无解情形，省掉一个容易写错的分支，这是半开区间写法的直接好处。
- 二分的上界要能给出证明。 $f(5m) \ge m$ 这一句就足以说明 $5(k+1)$ 够用；面试里被问「你怎么知道 hi 取这么大就行」时，答不上来会很被动。
- 越界风险出现在上界表达式而非中点。
5 * (k + 1)在int下就已经溢出，很多人只记得防(lo + hi) / 2却漏了这里。- 面试视角：讲述顺序应该是「先说 $f$ 怎么算（因子 5 计数）→ 再说 $f$ 单调 → 所以解集是区间 → 所以两次二分求端点」。如果面试官追问「答案为什么只可能是 0 或 5」，就用 $f$ 只在 5 的倍数处跳变来回答；这道追问几乎必然出现，是本题从「会写二分」区分到「真的理解」的分水岭。
易错点总结
- 错误写法：
long hi = 5 * (k + 1) + 5;忘了5L→ 用例k = 1000000000，5 * (k+1)在int下溢出为负数，hi变成负值，两次二分立刻返回 0，输出 0 而期望 5。- 错误写法：
countZero的参数用int→ 用例k = 1000000000时mid约为 $2.5 \times 10^9$，传参时被截断成负数，while (x > 0)直接不进入，返回 0，二分区间收缩方向全错。- 错误写法：
countZero写成count += x / 5却忘了更新x→ 死循环，程序超时。- 错误写法：
countZero写成while (x >= 5)且先累加后除 → 用例x = 25，第一轮加 25 再除得 5，第二轮加 5 再除得 1，返回 30，完全不是零的个数（正确为 6）。- 错误写法：
upperBound的条件写成countZero(mid) >= k，与lowerBound相同 → 用例k = 3，两次二分都返回 15，差为 0，输出 0 而期望 5。- 错误写法：
lowerBound里满足条件时写hi = mid - 1→ 用例k = 3，当mid = 15恰好是答案时被排除，最终返回 16，与upperBound的 20 相减得 4，答案偏小。- 错误写法：循环条件写成
lo <= hi但仍用hi = mid→ 用例任意k，当lo == hi == mid时hi被赋成自身，区间不再收缩，死循环。- 错误写法：认定答案只能是 0 或 5，于是写成「若
countZero(lowerBound(k)) == k返回 5 否则返回 0」但lowerBound上界取小了 → 用例k = 0，若上界写成5 * k则hi = 0，二分直接返回 0，countZero(0) = 0 == k判为有解返回 5，虽然结果碰巧对，但k = 1时hi = 5，边界擦着极限走，稍有改动就漏解。- 错误写法：忽略 $x = 0$，二分下界从 1 开始 → 用例
k = 0，正确解集是 ${0,1,2,3,4}$ 共 5 个，从 1 开始搜索得到 $[1, 5)$ 共 4 个，输出 4。- 错误写法：最终
return (int)(right - left)前把right、left先转成int再相减 → 用例k = 1000000000时两个边界都约 $5 \times 10^9$，各自截断后相减得到的差不再是 5，输出随机值。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 同样是两次边界二分求区间，但单调序列直接给出，无需自己构造 $f$ |
| 172. 阶乘后的零 | 中等 | 只需正向计算 $f(x)$，是本题的子过程 |
| 668. 乘法表中第k小的数 | 困难 | 二分的是答案值，判定函数是「不超过 mid 的元素个数」，属于二分答案而非二分下标 |
| 1201. 丑数 III | 中等 | 判定函数要用容斥原理统计倍数个数，单调性来源不同 |