## 一.题目描述 Given an integer n, return the number of trailing zeroes in n!. Note: Your solution should be in logarithmic time complexity. ## 二.题目分析 题目的要求是，给定一个整数`n`，找出`n!`结果的末尾为`0`的数的个数。暴力法是首先求出`n!`，然后直接计算末尾`0`的个数。（重复(n!)/10，直到余数非0为止），若输入的`n` 值过大时，在计算阶乘时会导致溢出，因此该方法并不好用。 [http://www.cnblogs.com/ganganloveu/p/4193373.html](http://www.cnblogs.com/ganganloveu/p/4193373.html) 给出一种很巧妙的解决方法： 事实上，只要对`n`的阶乘`n!`，做因数分解：`n!=2^x*3^y*5^z*...` 显然`0`的个数等于`min(x,z)`，并且经证明，可以得到：`min(x,z)==z` 。 例如： `n = 5`时，`5!`的质因数分解：`5! = 2 * 2 * 2 * 3 * 5` 中包含`3`个`2`、`1`个`3`和`1`个`2`。后缀`0`的个数是`1`。 `n = 11`时，`11!`的质因数分解：`11! = 2^8 * 3^4 * 5^2 * 7` 中包含`8`个`2`、`4`个`3`和`2`个`5`。后缀`0`的个数是`2`。 证明： 对于阶乘而言，也就是`1*2*3*...*n`，设`[n/k]`代表`1~n`中能被k整除的个数  显然有，`[n/2] > [n/5]` (左边是逢`2`增`1`，右边是逢`5`增`1`)  `[n/2^2] > [n/5^2]`(左边是逢`4`增`1`，右边是逢`25`增`1`)  ……  `[n/2^p] > [n/5^p]`(左边是逢`2^p`增`1`，右边是逢`5^p`增`1`)  随着幂次`p`的上升，出现`2^p`的概率会远大于出现`5^p`的概率。  因此左边的加和一定大于右边的加和，也就是`n!`质因数分解中，`2`的次幂一定大于`5`的次幂。 ## 三.示例代码 ~~~ #include <iostream> using namespace std; class Solution{ public: int trailingZeroes(int n) { int result = 0; while (n) { result += n / 5; n /= 5; } return result; } }; ~~~ ## 四.小结 这道题的代码很少，但是要从题目中把复杂的要求转化为简单的运算是需要推导的，总体来说还是需要费一定的功夫。