## 一.題目描述 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; } }; ~~~ ## 四.小結 這道題的代碼很少，但是要從題目中把復雜的要求轉化為簡單的運算是需要推導的，總體來說還是需要費一定的功夫。