172. 阶乘后的零

172.阶乘后的零

题目描述：

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

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

数据范围：

$0\le n \le 10^4$

题解：

$n!$ 中尾零的个数，关键是要找质因子 $5$ 的个数和 $2$ 的个数。就是需要找出 $[1,n]$ 中每个数的质因子 $5$ 的个数和 $2$ 的个数，然后累加，答案就是较小的那个。

考虑 $[1,n]$ 中质因子 $p$ 的个数：

$[1,n]$ 中 $p$ 的倍数有 $n_1 = \lfloor \frac{n}{p} \rfloor$ 个，至少有 $n_1$ 个数有一个 $p$ 。 $p^2$ 的倍数有 $n_2 = \lfloor \frac{n}{p^2} \rfloor$ ，至少有 $n_2$ 个数有两个 $p$ 。其中 $n_1$ 和 $n_2$ 有重复部分，可以只统计新增的个数。比如 $n_1$ 为至少有一个 $p$ 的个数， $n_2$ 为至少有两个 $p$ 的个数，其实是在 $n_1$ 的基础之上有 $n_2$ 个数增加了一个 $p$ 。也就是 $p$ 的总数增加了 $n_2$ 。

因此 $[1,n]$ 中质因子 $p$ 的个数为： $\sum_{k = 1} \lfloor \frac{n}{p^k} \rfloor$

$p$ 越大，质因子个数越少， $[1,n]$ 中质因子 $5$ 的个数是小于 $2$ 的个数的。

只需要统计质因子 $5$ 的个数就行。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    int trailingZeroes(int n)
    {
        int cnt = 0;
        while(n)
        {
            cnt += n / 5;
            n /= 5;
        }
        return cnt;
    }
};