# 【CSES】1618. Trailing Zeros

## [題目連結](https://cses.fi/problemset/task/1618)

## **時間複雜度**

* $O(1)$

## **解題想法**

這題會給你一個數字 $N$，請你算出 $N!$ 的尾巴有幾個零，看到 $N!$ 就知道直接乘出來是一個不切實際的作法，而且一看到測資範圍在 $1 \le N \le 10^9$ 的時候就應該要知道如果想要 <span style="color: green">**AC**</span> 這一題勢必是要用小於 $\le O(1)$ 的方式解

所以這題的正確做法其實是去關注 $N!$ 的質因數分解中 5 的冪次並直接輸出就可以了

這邊會直接輸出 5 的冪次的原因是從數學的角度來看，我們知道一個數的尾巴有幾個零取決於一個數分解開後有幾個 10 相乘

但因為 10 不是質數，所以我們要將 10 分解成兩個質數 2 跟 5 相乘，其中 2 的冪次必定大於等於 5，所以我們只要關注 5 的冪次即可

## **完整程式**

/* Question : CSES 1618. Trailing Zeros */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e8 + 50;
const int Mod = 1e9 + 7;
int n, ans, two, five, tmp;

signed main(){
    opt;
    cin >> n;
    for( int i = 5 ; i <= n ; i += 5 ){
        tmp = i;
        while( tmp % 5 == 0 ){
            ans++;
            tmp /= 5;
        }
    }

    cout << ans << "\n";
}