172. 阶乘后的零 : 经典统计质因数运用题

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目描述

这是 LeetCode 上的 172. 阶乘后的零 ，难度为 中等。

Tag : 「数学」

给定一个整数 $n$ ，返回 $n!$ 结果中尾随零的数量。

提示 $n! = n * (n – 1) * (n – 2) * … * 3 * 2 * 1$

示例 1：

输入：n = 3

输出：0

解释：3! = 6 ，不含尾随 0
复制代码

示例 2：

输入：n = 5

输出：1

解释：5! = 120 ，有一个尾随 0
复制代码

示例 3：

输入：n = 0

输出：0
复制代码

提示：

• $0 <= n <= 10^4$

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

数学

对于任意一个 $n!$ 而言，其尾随零的个数取决于展开式中 $10$ 的个数，而 $10$ 可由质因数 $2 * 5$ 而来，因此 $n!$ 的尾随零个数为展开式中各项分解质因数后 $2$ 的数量和 $5$ 的数量中的较小值。

即问题转换为对 $[1, n]$ 中的各项进行分解质因数，能够分解出来的 $2$ 的个数和 $5$ 的个数分别为多少。

为了更具一般性，我们分析对 $[1, n]$ 中各数进行分解质因数，能够分解出质因数 $p$ 的个数为多少。根据每个数能够分解出 $p$ 的个数进行分情况讨论：

• 能够分解出至少一个 $p$ 的个数为 $p$ 的倍数，在 $[1, n]$ 范围内此类数的个数为 $c_1 = \left \lfloor \frac{n}{p} \right \rfloor$
• 能够分解出至少两个 $p$ 的个数为 $p^2$ 的倍数，在 $[1, n]$ 范围内此类数的个数为 $c_2 = \left \lfloor \frac{n}{p^2} \right \rfloor$
• …
• 能够分解出至少 $k$ 个 $p$ 的个数为 $p^k$ 的倍数，在 $[1, n]$ 范围内此类数的个数为 $c_k = \left \lfloor \frac{n}{p^k} \right \rfloor$

我们定义一个合法的 $k$ 需要满足 $p^k \leqslant n$，上述的每一类数均是前一类数的「子集」（一个数如果是 $p^k$ 的倍数，必然是 $p^{k-1}$ 的倍数），因此如果一个数是 $p^k$ 的倍数，其出现在的集合数量为 $k$，与其最终贡献的 $p$ 的数量相等。

回到本题，$n!$ 中质因数 $2$ 的数量为 :