YSMull
<-- algorithm



原题链接

2021/04/12

解法一

因子 5 的个数一定比 2 多，所以只需要统计有多少个 5

考察 28 的阶乘：

5 10 15 20 25
1 1  1  1  2

一共有 6 个 5，所以结尾有 6 个零。

impl Solution {
    pub fn trailing_zeroes(n: i32) -> i32 {
        let mut zero = 0;
        for mut fac_5 in (5..=n).step_by(5) {
            while fac_5 % 5 == 0 {
                fac_5 /= 5;
                zero += 1;
            }
        }
        return zero;
    }
}

解法二

每隔 5 个数有 1 个因子 5 ($\frac{n}{5}$个)
每隔 25 个数有 2 个因子 5 ($\frac{n}{25}$个, 这里不用乘以$2$，因为$\frac{n}{5}$的时候算过一遍)
每隔 125 个数有 3 个因子 5 ($\frac{n}{125}$个，这里不用乘以$3$，因为$\frac{n}{5}$的时候算过一遍，$\frac{n}{25}$的时候算过一遍)
…

\[\lfloor\frac{n}{5}\rfloor + \lfloor\frac{n}{25}\rfloor + \lfloor\frac{n}{125}\rfloor + \cdots\] 
impl Solution {
    pub fn trailing_zeroes(mut n: i32) -> i32 {
        let mut zero = 0;
        while n > 0 {
            zero += n / 5;
            n /= 5;
        }
        return zero;
    }
}

解法二的筛法理解

我们要求的是 n! 分解质因数后 5 的指数。

第一轮，我们先把 1~n 中所有能被 5 整除的数筛出来，可以筛出$\lfloor\frac{n}{5}\rfloor$个数。
第二轮，我们把上一轮筛除来的所有的数都除以 5，得到了一个新数组，这个新数组中可能还有一些数是 5 的倍数（没筛干净），那么重复第一轮的方式筛出来，直到第二轮筛不出 5 的倍数为止。

解法二的子问题理解

我们定义$f(n)$为整数$n$分解质因数后$5$的指数。
那么

\[\begin{aligned} f(n!) &= f(1 \times 2 \times 3 \times \cdots \times n) \\ &= f(5 \times 10 \times 15 \times \cdots) \\ &= f(5^{\lfloor\frac{n}{5}\rfloor} \times 1 \times 2 \times 3 \times \cdots \times \lfloor\frac{n}{5}\rfloor) \\ &= f(5^{\lfloor\frac{n}{5}\rfloor} \times \lfloor\frac{n}{5}\rfloor!) \\ &= {\lfloor\frac{n}{5}\rfloor} + f(\lfloor\frac{n}{5}\rfloor!) \end{aligned}\]

这样，我们就把 $f(n!)$ 变成了 $f(\lfloor\frac{n}{5}\rfloor!)$ 这个子问题。