Try   HackMD

【CSES】1618. Trailing Zeros

題目連結

時間複雜度

  • O(1)

解題想法

這題會給你一個數字

N,請你算出
N!
的尾巴有幾個零,看到
N!
就知道直接乘出來是一個不切實際的作法,而且一看到測資範圍在
1N109
的時候就應該要知道如果想要 AC 這一題勢必是要用小於
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"; }