看到“793. 阶乘函数后 K 个零”这个题名，很多人第一反应是：又是阶乘？那把 n! 算出来，数一数尾部有多少个零不就行了？如果真这么想，这道题基本就进了死胡同。793 题真正要考的不是大数运算，而是二分答案模型，而且是从“第K小 / 第K大”那一类问题里衍生出来的边界判断。简单说，这题是给你一个目标值 K，问你“有多少个 n 的阶乘末尾恰好有 K 个零”，答案是 0 或 5，但关键不是背结论，而是搞清楚为什么能用二分、怎么用二分把“恰好等于”拆成两个边界。
这篇文章我会从题面拆解开始，把阶乘尾零的计数原理、单调性证明、二分边界模板完整过一遍，最后附上我自己调试时的踩坑记录。无论是准备算法面试，还是想系统梳理二分答案这一类题的套路，这篇都值得花十分钟读完。
1. 题面拆解：这道题到底要我们干什么
1.1 核心问题：不要求算阶乘，而是在数“平台”
输入是一个非负整数 K，输出满足下面条件的非负整数 x 的个数：
x! 的十进制表示末尾恰好有 K 个 0。
比如 K = 0 时，0! = 1，1! = 1，2! = 2，3! = 6，4! = 24，它们的末尾都是 0 个零，而 5! = 120 末尾有 1 个零，所以答案是 5。
这里有个容易忽略的细节：题目问的是“恰好有 K 个零”。不是“至少 K 个零”，也不是“第 K 个零出现在哪里”。这个“恰好”决定了我们不能简单二分查找某个点，而是要回头找一段连续区间，看这段区间有多长。
我习惯把这类函数画成一条台阶：x 越大，x! 尾零数只增不减，但它不是每次加 1，而是有时候一步跨好几级。于是就会形成很多“平台”，每个平台对应一段连续的 x，它们的尾零数相同。题目问的就是：高度为 K 的那一级平台，长度是多少。
理解成平台之后，这个问题就和“在一个非递减数组里找某个值出现的次数”一模一样了。只不过数组不是直接给的，而是由一个函数 f(x) 隐式定义的。
1.2 为什么不能硬算：阶乘爆炸与单调性是破局点
不少人第一反应是：枚举 x，边乘边统计 2 和 5 的因子个数，直到尾零数超过 K。这个思路在小数据下没毛病，但 K 的上限很大，x 也会非常大。n! 的增长速度是指数级以上，根本没法真的把阶乘展开。就算只统计因子个数，枚举的区间也可能长达上亿，时间上完全扛不住。
真正破局的关键，是 f(x) 具有单调性：
f(x + 1) ≥ f(x)。
因为 (x + 1)! = x! × (x + 1)，乘以一个正整数只会增加因子 2 和 5 的个数，不会减少。所以 f(x) 是一个非递减函数。单调函数就可以二分，这是所有“二分答案”题目的共同基础。
你不需要知道每个 x! 具体等于多少，只需要一个能快算 f(x) 的函数，以及一个能快速验证“f(mid) 是否达到 K”的判断条件。剩下的，就是把二分模板套上去。
1.3 解题方向：二分答案在这里二分的是“位置”，不是“值”
常见的二分答案题，是“在值域里猜答案”。比如求第 K 小元素，你猜一个值 mid，然后统计小于等于 mid 的元素个数，和 K 比较，从而缩小区间。
793 题稍微绕一点：我们不知道 x 的范围，但知道 f(x) 单调。于是可以反过来，二分“位置 x”，找到一个左边界 L，使得 f(L) ≥ K 且 L 尽可能小；再找一个右边界 R，使得 f(R) ≥ K + 1 且 R 尽可能小。答案就是 R - L。
这就是“等于 K 的个数 = lower_bound(K + 1) - lower_bound(K)”的来源。先把这个公式记住，后面我会一步步推。
2. 核心原理：阶乘尾部零的个数与单调性
2.1 尾零只和因子 10 有关，关键是数 5
一个十进制数末尾有一个 0，就说明它能被 10 整除一次；有两个 0，说明能被 100 整除。10 = 2 × 5，所以 x! 末尾零的数量，等于 x! 分解质因数后“2 × 5”的对数。
问题来了：x! 里因子 2 多还是因子 5 多？显然是 2 多。因为每两个数就有一个偶数，而每五个数才有一个 5 的倍数。所以 5 是稀缺资源，2 永远管够。结论是：
x! 末尾零的数量 = x! 中因子 5 的数量。
你可以把它想象成流水线组装：2 号零件产量极高，5 号零件产量低，最终成品的数量由 5 号零件决定。数 5 的个数，就是数这条流水线能产出多少个成品。
2.2 经典计数公式：不停除以 5 再累加
怎么快速数出 x! 里有多少个因子 5？答案是：
f(x) = ⌊x / 5⌋ + ⌊x / 25⌋ + ⌊x / 125⌋ + ...
为什么这么算？因为 1 到 x 之间，5 的倍数有 ⌊x / 5⌋ 个，每个至少贡献一个因子 5；25 的倍数有 ⌊x / 25⌋ 个，每个再多贡献一个因子 5；125 的倍数同理。把它们的贡献全部加起来，就是总因子 5 的数量。
写成代码就是经典的尾零计数函数：
def count_zeros(x: int) -> int: cnt = 0 while x: x //= 5 cnt += x return cnt注意循环里是先整除 5，再累加商。第一次累加所有 5 的倍数的贡献，第二次累加 25 的倍数的额外贡献，第三次累加 125 的倍数的额外贡献。循环次数是 O(log₅ x)，非常快。
这套写法很多人见过，但容易忽略一个前提：x 必须是非负整数。x = 0 时，while 循环不执行，cnt = 0，正好对应 0! = 1 的尾零数。
2.3 单调性与“平台”现象：为什么答案不是 0 就是 5
f(x) 单调不减，我们已经说过。但这里还有更有意思的现象：它并不严格递增。
举个例子：
f(0) = 0，f(1) = 0，f(2) = 0，f(3) = 0，f(4) = 0。这一段五个数全都落在“尾零数为 0”的平台上。
f(5) = 1，f(6) = 1，f(7) = 1，f(8) = 1，f(9) = 1。这又是一段五个数的平台。
f(10) = 2，一直到 f(14) = 2，平台长度还是 5。
但到了 25!，情况变了。因为 25 是 5 的平方，多贡献了一个因子 5，f(25) = 6。于是你会发现，从 f(24) = 4 直接跳到 f(25) = 6，中间的“尾零数为 5”这个高度没有任何 x 对应。所以 K = 5 时，答案是 0。
这里有个严谨结论：由于每连续五个整数里，至少有一个包含因子 5，所以 f(x + 5) ≥ f(x) + 1。也就是说，任何“平台”的长度都不可能超过 5；同时，因为跳变可能跨过某个整数高度，所以有些 K 的答案是 0，有些 K 的答案正好是 5。这也是为什么原题的返回值永远是 0 或 5。
我早期刷题时，看到“答案不是 0 就是 5”这个特性后，一度想直接特判：如果 count_zeros(5 * K) == K 就返回 5，否则返回 0。这个写法确实能过，因为它依赖的正是“平台长度最大为 5”这个性质。但我还是推荐老老实实用二分边界方法，原因有二：第一，边界方法不需要背这个特殊结论，普适性更强；第二，很多变种题会改成问“第 K 个满足条件的 x”，那时候直接特判就不够用了，二分模板才能迁移过去。
3. 二分答案建模：怎样把“恰好等于 K”转化成两个边界
3.1 先看第 K 小 / 第 K 大的通用二分模板
在进入 793 题之前，我想先把二分答案的通用框架摆出来。因为 793 题本质上就是这个框架的一个变体。
第 K 小问题的标准解法是：在值域 [L, R] 上二分，每次取中点 mid，统计“小于等于 mid 的元素个数” count(mid)，然后比较 count(mid) 和 K 的大小。如果 count(mid) ≥ K，说明第 K 小元素不会大于 mid，于是收缩右边界；否则收缩左边界。
模板长这样：
def kth_smallest(L: int, R: int, K: int, count) -> int: while L < R: mid = (L + R) // 2 if count(mid) >= K: R = mid else: L = mid + 1 return L这个模板的核心是：count(mid) 必须是单调不减的。也就是说，mid 越大，小于等于 mid 的元素个数只会越多，不会变少。K 是目标，二分逼近的是“第一个让 count(mid) ≥ K 的位置”。
你可能已经发现了，这个模板根本不关心元素本身长什么样，只关心两件事：第一，能不能快速算出 count(mid)；第二，count(mid) 是否随 mid 单调不减。如果一个题目满足这两点，就可以套二分答案。
3.2 把“恰好等于 K”拆成 lower_bound(K + 1) - lower_bound(K)
现在回到 793 题。我们想要的是 f(x) = K 的 x 的个数。
由于 f(x) 单调不减，所有满足 f(x) ≥ K 的 x 是从某个位置开始一直延展到无穷的；所有满足 f(x) ≥ K + 1 的 x 也是从某个位置开始延展到无穷的。那么“f(x) ≥ K 的区间”减去“f(x) ≥ K + 1 的区间”，剩下的就是“K ≤ f(x) < K + 1”的区间。
又因为 f(x) 是整数，所以 K ≤ f(x) < K + 1 等价于 f(x) = K。于是：
答案 = lower_bound(K + 1) - lower_bound(K)
其中 lower_bound(t) 返回的是：
最小的 x，使得 f(x) ≥ t。
这个减法的图形语义就是：先找到尾零数“爬到 K 级”的位置，再找到尾零数“爬到 K + 1 级”的位置，两个位置之间夹着的，就是恰好停在 K 级平台上的所有 x。
用有序数组类比就是：在一个排好序的数组里找某个值出现的次数，标准做法是 upper_bound - lower_bound。这里 upper_bound(K) 就是第一个 > K 的位置，等于 lower_bound(K + 1)。因为数组里元素是整数，> K 和 ≥ K + 1 完全等价。
所以在代码里，不需要单独实现一个 upper_bound，只要把目标值改成 K + 1，再用同一个 lower_bound 函数即可。
3.3 完整代码实现：Python 与 C++ 双版本
有了 lower_bound 这个抽象，代码写起来就非常整齐。
def count_zeros(x: int) -> int: cnt = 0 while x: x //= 5 cnt += x return cnt def lower_bound(target: int) -> int: left, right = 0, 5 * target + 1 while left < right: mid = (left + right) // 2 if count_zeros(mid) >= target: right = mid else: left = mid + 1 return left def preimageSizeFZF(K: int) -> int: return lower_bound(K + 1) - lower_bound(K)C++ 版本要特别注意溢出问题，因为 K 最大可以到十亿量级，5 * K + 1 会超过 int 的表示范围：
class Solution { public: long long countZeros(long long x) { long long cnt = 0; while (x) { x /= 5; cnt += x; } return cnt; } long long lowerBound(int target) { long long left = 0, right = 5LL * target + 1; while (left < right) { long long mid = left + (right - left) / 2; if (countZeros(mid) >= target) right = mid; else left = mid + 1; } return left; } int preimageSizeFZF(int K) { return (int)(lowerBound(K + 1) - lowerBound(K)); } };这段 Python 代码里，lowerBound 里传入的 target 分别是 K 和 K + 1。注意 target 是 int，但 right 我直接写成 5 * target + 1，在 Python 里没有溢出烦恼；C++ 里必须先转成 5LL * target，不然乘法结果会溢出。
为什么 right 要设置成 5 * target + 1？下一节专门讲。
4. 二分边界与上界选择：这些细节决定了代码对不对
4.1 二分上界为什么是 5 * target + 1
二分的前提是答案落在 [left, right) 这个区间里。left = 0 显然没问题，因为 f(0) = 0。关键是 right 选多大，才能保证f(right - 1) >= target。
我们的 lower_bound 要找的是“第一个满足 f(x) ≥ target 的 x”。如果能证明 f(5 * target) 一定 ≥ target，那么所有解都落在 [0, 5 * target] 内，right 取 5 * target + 1 就不会漏。
证明非常简单：
f(5 * target) = ⌊5 * target / 5⌋ + ⌊5 * target / 25⌋ + ...
第一项就是 target，后面每项都是非负数，所以：
f(5 * target) ≥ target
所以第一个满足条件的位置，一定不超过 5 * target。right = 5 * target + 1 作为左闭右开区间的右边界，永远足够。
这里我要多说一句：上界选大一点行不行？行。比如直接设 right = 10^18，二分 60 多次也能出结果。但选 5 * target + 1 的好处是循环次数更少，而且这个上界本身提供了一种“数学上界依赖目标值”的思维方式，面试时说出来会很加分。
如果你担心 target = 0 时 right = 1 会不会漏，不会。因为 f(0) = 0 已经满足 ≥ 0，lower_bound(0) 的结果就是 0。代码里 right = 1，mid = 0，count_zeros(0) >= 0，right 收缩到 0，循环退出，返回 0，正确。
4.2 特殊值 K = 0 为什么不值得单独特判
很多人看到 K = 0 会慌：0! = 1，末尾确实 0 个零，那有多少个 n 满足条件？n = 0, 1, 2, 3, 4 都满足，答案是 5。
用 lower_bound 公式算一下：
lower_bound(1) = 5，因为 f(0) = 0 < 1，f(5) = 1 ≥ 1，第一个满足条件的是 5。
lower_bound(0) = 0，因为 f(0) = 0 ≥ 0，第一个满足条件的是 0。
答案 = 5 - 0 = 5，完全正确。
所以 K = 0 不需要单独 if 分支，模板天然处理。我见过不少代码在这里加了特判，反而多了一个容易出错的路径。能用统一模板覆盖的分支，尽量不要单独写。
4.3 防溢出的两个关键细节
第一个细节是 mid 的计算。C++ 里(left + right) / 2在某些极端情况下会溢出，虽然这道题 left 和 right 都在 5e9 量级，两个加起来也超过 int 上限，所以一定要用left + (right - left) / 2，或者用 long long 后再相加。我用的是前者，这个习惯建议养成，因为以后遇到值域更大的题也能直接用。
第二个细节是乘法溢出。right = 5 * target + 1 这里，如果 target 是 int，5 * target 会先按 int 计算再赋给 long long，就晚了。必须先让其中一个操作数变成 long long，比如 5LL * target，或者显式转成 long long。这个 bug 非常隐蔽，因为 K 小的时候测不出来，K 一大就崩。
另外，count_zeros 函数传入的 x 是 long long，因为二分过程会访问到 5e9 级别的数。如果这里还用 int，右边的赋值也会截断，结果就完全错了。我在本地第一次跑 C++ 版本时就踩了这个坑，排查了好一会儿才想起来是类型问题。
4.4 复杂度为什么是 O(logK · logK)
每次 count_zeros(mid) 的时间是 O(log₅ mid)，约等于 log₅(5K)，也就是 O(logK)。二分的轮数是 O(log(5K))，也是 O(logK)。所以整体复杂度是 O(logK · logK)。
K 最大 1e9 时，外层二分大概 30 多次，内层除以 5 大概 13 次，总共几百次计算，比枚举不知道快到哪里去了。这也是为什么我强调“不要硬算阶乘”——数据的规模早就决定了你要用二分。
5. 踩坑记录与模板化打法：从 793 题看“第K小 / 第K大”家族
5.1 常见错误速查表
我把调试时遇到的典型错误整理成了一张表，照着我自己的血泪史写的：
| 症状 | 原因 | 修正方法 |
|---|---|---|
| 大 K 下答案异常 | int 溢出，5 * K + 1 截断 | 使用 long long，写 5LL * target |
| 二分死循环 | 循环条件写成 left <= right | 统一用左闭右开 while (left < right) |
| lower_bound 结果偏大 | mid 计算溢出 | 用 left + (right - left) / 2 |
| count_zeros 死循环 | 忘记 x //= 5，x 一直不变 | 确保循环体内 x 会缩小 |
| 答案差 1 | 用 lower_bound(K) - lower_bound(K - 1) 但没处理边界 | 改成 lower_bound(K + 1) - lower_bound(K) |
| 结果不是 0 就是 5 却不一致 | 上界不够大，漏掉了真正的边界 | 上界取 5 * target + 1 |
最后一条值得展开：如果你上界取得不够，比如 right = K + 1，那么对于某些 K，第一个 f(x) ≥ K 的位置可能远大于 K + 1，二分就会返回一个错误的小值。表现就是答案偶尔对、偶尔错，特别让人头疼。上界一定要有理论依据，不能随手写个 K 就完事。
5.2 手动验证几个关键 K 值
为了确认模板没写错，我建议刷题时至少手动验证几个临界数据。这里列几个我验证过的：
| K | lower_bound(K) | lower_bound(K + 1) | 答案 |
|---|---|---|---|
| 0 | 0 | 5 | 5 |
| 1 | 5 | 10 | 5 |
| 4 | 20 | 25 | 5 |
| 5 | 25？不对，f(25) = 6，所以 lower_bound(5) 也是 25，lower_bound(6) 也是 25 | 25 - 25 = 0 | 0 |
| 6 | 25 | 30 | 5 |
| 10 | 45 | 50 | 5 |
| 11 | 50？f(50) = 12，lower_bound(11) = 50，lower_bound(12) = 50，答案 0 | 50 - 50 = 0 | 0 |
注意 K = 5 这一行：f(24) = 4，f(25) = 6，所以 f(x) ≥ 5 的第一个 x 是 25；f(x) ≥ 6 的第一个 x 也是 25。两个 lower_bound 都是 25，差值 0，说明没有 x 满足 f(x) = 5。
K = 10 这一行：f(45) = 9 + 1 = 10，f(49) = 9 + 1 = 10，f(50) = 10 + 2 = 12，所以 f(x) ≥ 10 的第一个 x 是 45，f(x) ≥ 11 的第一个 x 是 50，差值 5。
这些手算过程不需要每次都做，但至少挑一两个 K 走一遍，能帮你确认“为什么答案是 R - L”而不是其他写法。
5.3 把模板推广到其他“第K小 / 第K大”场景
793 题做完之后，最值钱的不是记住这套代码，而是提炼出更一般的套路：只要一个函数 count(mid) 能表示“候选值 mid 时满足条件的个数”，并且 count(mid) 随 mid 单调不减，就可以二分逼近第 K 个满足条件的位置。
我自己刷题时的习惯是，把下面这个骨架存在本地，遇到新题直接往里套：
def solve(L: int, R: int, K: int) -> int: while L < R: mid = (L + R) // 2 if count_leq(mid) >= K: R = mid else: L = mid + 1 return L唯一的难点是设计 count_leq(mid)。在 793 题里，count_leq 就是 count_zeros(mid)，只不过这里“小于等于”变成了“f(mid) ≥ target”，因为目标反过来变成了位置。
这类题还有一些常见的变体，比如：
- 求“最大值最小化”问题，check(mid) 判断是否存在一种方案让最大值不超过 mid；
- 求“第 K 小的横坐标差值”，check(mid) 统计差值不超过 mid 的数对数量；
- 求“满足条件的最小速度 / 最小容量”，check(mid) 模拟一下能否完成任务。
它们的共同点都是：猜一个答案，验证它是否满足条件，然后根据“满足”或“不满足”收缩区间。793 题的独特之处在于它用二分找的是“边界差”，而不是单个答案，这个视角对理解二分答案的本质很有帮助。
最后分享一个我自己的小习惯：看到“恰好等于 K”的计数题，第一反应不是去推精确公式，而是想“这个函数单调吗？能不能用二分找两个边界？”只要单调性成立，就把“等于 K”拆成两次 lower_bound，一次查 K，一次查 K + 1，两者相减就是答案。这套思路我后来在不少计数类二分题里都在用，越用越顺手。793 题是练习这个思路的绝佳样本，值得多写几遍。
