前言

想要计算阶乘后的0有多少，可以直接算出阶乘值，再不断对10取余。但是如果n比较大，这种方法是根本行不通的，只能挖掘规律。

一、阶乘后的零

二、挖掘规律

1、动态规划

想要得到0，等价于得到10，再等价于得到2 * 5，而5的个数一定比2多，毕竟偶数太多。

所以有了5的个数，就有了2*5的个数，就有了10的个数，自然而然就得到0的个数。
如何寻找5的个数，当i % 5 == 0时，f[i] = f[i / 5] + 1

func trailingZeroes(n int) int {f := make([]int,n + 1)rs := 0for i := 1;i <= n;i++ {if i % 5 == 0 {f[i] = f[i / 5] + 1rs += f[i]}}return rs
}

2、直接寻找5的个数

[1,n]中一共有m₁个5的倍数，易知，m₁ = floor(n / 5)，还有25的倍数m₂ = floor(n / 25)，125的倍数m₃=floor(125)，这些5^k除去前面包含的5^k-1，还剩一个5。
所以[1,n]中有m = m₁ + m₂ + … + m_k个5的质因数。

func trailingZeroes(n int) int {rs := 0for n > 0 {rs += n / 5n /= 5}return rs
}

总结

1）挖掘题目规律，才能转换问题，简化问题，比如求5的质因数。而后序通过动态规划来求，还是继续找规律求，又是另一回事了。

参考资料

[1] LeetCode 阶乘后的零