🔥码云GVP开源项目 12k star Uniapp+ElementUI 功能强大 支持多语言、二开方便! 广告
## 一.题目描述 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; } }; ~~~ ## 四.小结 这道题的代码很少,但是要从题目中把复杂的要求转化为简单的运算是需要推导的,总体来说还是需要费一定的功夫。