d122. Oh! My Zero!!

給一正整數 n
輸出 $n!$ 末尾 0 的個數

---

解法一

計算 $n!$ 的質因數 5 的個數
因為 $5 × 2 = 10$
而質因數 2 的個數一定會 > 5 的個數
所以每個 5 都會使尾部多一個 0

質因數 5 個數 $= \left \lfloor \frac{n}{5} \right \rfloor + \left \lfloor \frac{n}{5^{2}} \right \rfloor + \left \lfloor \frac{n}{5^{3}} \right \rfloor ...$

數學解釋

$n! = 1 \times 2 \times 3 \times … \times n$
每出現一個 5，就貢獻一個 5 的因數

但有些數會貢獻 多個 5
比如：25, 50, 125, 625…

因此
先數 能被 $5$ 整除的數 有多少個
再數 能被 $5^{2}$ 整除的數 有多少個
…
再數 能被 $5^{k}$ 整除的數 有多少個

直到 $5^{k} > n$

✅ 完整代碼

評分結果(參考) ： AC (1ms, 300KB)

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, cnt;
    
    while(cin >> n){
        cnt = 0;
        while(n > 0){
            n /= 5;
            cnt += n;
        } 
        cout << cnt << "\n";
    }

    return 0;
}