[leetcode_172]Factorial Trailing Zeroes

计算n!的尾部有多少个连续的0，实际上问题可以准换为，分解质因数后，有多少个5(因为2比5多)。但是计算机5的时候有技巧，如果直接每个数模的话会超时，实际上只需要计算5^k次与n的关系即可。

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


class Solution {
public:
    int trailingZeroes(int n) {
        vector<int> five(14);
        for (int i = 1; i <= 13; i++) {
            five[i] = ((int)pow(5.0, i));
        }
        int before = 0;
        int count = 0;
        for (int i = 13; i >= 1; i--) {
            if (five[i] <= n) {
                count += (n / five[i] - before) * i;
                before = (n / five[i]);
            }
        }
        return count;
    }
};