这个题目本身并不难，但是题目的挑战对时间复杂度要求较高，不适合使用暴力解法；而且由于输入数据类型为 long，可能会有很大的测试数据，那么打表也不好用。但是这种数论入门题正好说明了数论题的解题思路，即使用数学工具简化问题，或者找出规律缩小问题规模。

题目描述

题目大意

设计一个算法，计算出 n 阶乘中尾部零的个数。

输入

1
2
3

5
11
1001171717

本题第 3 组数据是借由暴力算法的 TLE 提示结果得来的。

输出

1
2
3

1
2
250292920

解题思路

大数阶乘看似计算量大，但是仍可使用乘法规律合理简化问题。

数字末尾要是为零，那么必定能被 10 整除。但要注意 n! 能被 10 整除，也可能是因为 1~n 中有不能被 10 整除却能被 2 或 5 整除的数，毕竟 2 和 5 都是 10 的质因数。进一步说，能被 10 整除的数也一定可以分解出因数 2 和 5，且分解后不会对阶乘结果产生任何影响。这样能把问题分解为 n 个相似的小问题，但是每个小问题仍然需要进行因数分解以计数 2 和 5 的个数，实际的算法仍属于暴力解法，仅仅只是方便思考。

那么，不妨看看能不能把原问题分解为更加细小的问题：假设把 n! 的结果进行质因数分解，那么根据分解结果中 2 和 5 的数量就能确定最后有多少个 10 相乘，即结尾有多少个零。 现在，问题转化为 n! 中质因数 p（p = 2 或 5） 的个数怎么数。

下面就来使用递推方法探求新问题的解法： 那么 c1 = n / p 得到 1~n 中有 c1 个数是 p 的倍数； 这 c1 个数是必定为 p, 2p, 3p … c1p，那么它们都除以 p 可得到范围 1~c1，这个范围中能被 p 整除的数就代表了 1~n 中能被 p^2 整除的数，其数量可由 c2 = c1 / p 得到； … 直到最后，ck = ck-1 / p 使得 ck = 0，那么就找到了 n! 中素因子 p 的个数为 c1 + c2 + … + ck

那么，原问题就可以化为对 p 为 2 和 5 分别进行一次上述计算即可进一步算出最终结果。但是，计算之前还应发现上述计算实质是反复相除（可以仔细对比它和“辗转相除法”的异同），那么 p 为 2 的结果一定比 5 大，也就是说 2 的因数个数更多。但是必须 2 和 5 相乘才能产生结尾的零，所以我们其实只需要计算 p 为 5 的一种情况就可以了。

最后，可以直接估算出本算法的时间复杂度为 O(logN)，满足挑战要求。

代码展示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public class Solution {
    /*
     * @param n: An integer
     * @return: An integer, denote the number of trailing zeros in n!
     */
    public long trailingZeros(long n) {
        long re = 0L;

        while (n > 0L) {
          n /= 5;
          re += n;
        }
        return re;
    }
}