LeetCode 172. Factorial Trailing Zeroes

• 2020 年 2 月 14 日
• 筆記

題目

題意：問你一個數的階乘，末尾有多少0

題解：一個數的階乘結果的末尾的0，根據分解質因數，只能是25得到的，所以把這個數的階乘分解質因數，看有多少個25，2顯然是比5多的，所以數一數有多少個5就可以了。

比如24的階乘里分解質因數有幾個五呢？5 里有一個5，10，15，20里各有一個，一共4=24/5 個五。但是25 可以分解為5*5，所以25的階乘里分解質因數有4+2=6個五，

但是到了125，125有三個五，所以一個數n的階乘里有多少個五呢？

x = n/5 + n/25 + n/125 …..

class Solution {  public:      int trailingZeroes(int n) {            long long int x=5;          int ans=0;          while(x<=n)          {              ans+=n/x;              x*=5;          }            return ans;        }  };