Factorial Trailing Zeroes

原题链接Factorial Trailing Zeroes

计算n!(n的阶乘)末尾有多少个0

思路：

0实际上来源于10，而10来源于2×5，所以只需要判断 n×(n−1)×(n−2)×...×1 n × ( n − 1 ) × ( n − 2 ) × . . . × 1 <script type="math/tex" id="MathJax-Element-46">n×(n-1)×(n-2)×...×1</script>可以拆分成多少个 2×5 2 × 5 <script type="math/tex" id="MathJax-Element-47">2×5</script>即可。而2的个数明显多于5的个数，所以只需要判断有多少个5即可

考虑1到100这100个数可以分成多少个5

首先可以想到 5,10,15,20,...,100 5 , 10 , 15 , 20 , . . . , 100 <script type="math/tex" id="MathJax-Element-48">5,10,15,20,...,100</script>这 100/5=20 100 / 5 = 20 <script type="math/tex" id="MathJax-Element-49">100/5=20</script>个数可以分解成 5×m 5 × m <script type="math/tex" id="MathJax-Element-50">5×m</script>的形式，所以这20个数每个数都可以分出一个5来

其次考虑 25,50，75，100 25 , 50 ， 75 ， 100 <script type="math/tex" id="MathJax-Element-51">25,50，75，100</script>这 100/5/5=4 100 / 5 / 5 = 4 <script type="math/tex" id="MathJax-Element-52">100 / 5 / 5 = 4</script>个数可以分解成 5×5×m 5 × 5 × m <script type="math/tex" id="MathJax-Element-53">5×5×m</script>的形式，所以这4个数每个数又可以分出一个5来

注，由于计算5的倍数时25,50,75,100已经分解出一个5，所以计算25的倍数时仅剩下一个5可以分解

所以100!末尾0的个数就是5的个数即 100/5+100/5/5=24 100 / 5 + 100 / 5 / 5 = 24 <script type="math/tex" id="MathJax-Element-54">100/5 + 100/5/5 = 24</script>个

如果给出的n足够大，那么

• 可以分解成 5×m 5 × m <script type="math/tex" id="MathJax-Element-55">5×m</script>形式的数可以贡献出一个5，总共有 n/5 n / 5 <script type="math/tex" id="MathJax-Element-56">n/5</script>个
• 可以分解成 5×5×m 5 × 5 × m <script type="math/tex" id="MathJax-Element-57">5×5×m</script>形式的数可以贡献出一个5，总共有 n/5/5 n / 5 / 5 <script type="math/tex" id="MathJax-Element-58">n/5/5</script>个
• 可以分解成 5×5×5×m 5 × 5 × 5 × m <script type="math/tex" id="MathJax-Element-59">5×5×5×m</script>形式的数可以贡献出一个5，总共有 n/5/5/5 n / 5 / 5 / 5 <script type="math/tex" id="MathJax-Element-60">n/5/5/5</script>个
• …

最后计算总数量即可

代码如下

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        for(long long int i = 5; n / i > 0; i *= 5)
            res += n / i;
        return res;
    }
 };