http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4433

C++版本一

題解：這個(gè)題讓我想起了https://codeforces.com/contest/837/problem/D

https://blog.csdn.net/weixin_43272781/article/details/84581632

思路差不多，因?yàn)檫@個(gè)題5肯定比2少所以只要考慮5就行

不過我考慮了二分答案和每個(gè)數(shù)字前面5出現(xiàn)的情況所以感覺還行

就是內(nèi)存有點(diǎn)多，時(shí)間有點(diǎn)長(zhǎng)

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUGusing namespace std; typedef long long ll; const int N=20000000; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m; int a[N]; int sloved(int x){return x/5+x/25+x/125+x/625+x/3125+x/15625+x/78125+x/390625+x/1953125+x/9765625+x/48828125+x/244140625; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%d",&t);int T=0;while(t--){scanf("%d",&n);cout << "Case "<<++T<<": ";int l=5;int r=n*5;int mid ,ans=1;while(l<=r){mid=(l+r)>>1;int tmp=sloved(mid);if(tmp==n){cout << mid-mid%5 << endl;ans=0;break;}else if(tmp<n){l=mid+1;}else{r=mid-1;}}if(ans)cout << "impossible" << endl;}//cout << "Hello world!" << endl;return 0; }

?

C++版本二

題解：
二分枚舉n，若將階乘中所有的數(shù)拆分成質(zhì)因子的乘積，發(fā)現(xiàn)只有2*5 才能產(chǎn)生
0，同時(shí)2 會(huì)比5 的個(gè)數(shù)多。故直接二分n，check 5 的個(gè)數(shù)。

#include <stdio.h>int five[30]; int total_five;void init(){five[0] = 5;total_five = 1;for(int i = 1; five[i-1]*5ll<1e9; i ++) {five[i] = five[i-1]*5;total_five ++;} }int get_suff_count(int m){int ret = 0;for(int i = 0; i < total_five; i ++){ret += m/five[i];}return ret; }int bin(int l, int r, int Q){int ret = -1;while( l <= r){int m = (l+r) >> 1;int suff_count = get_suff_count(m);if(suff_count == Q){ret = m;r = m-1;}else if(suff_count < Q){l = m+1;}else{r = m-1;}}return ret; }int main(){ // freopen("data1.in", "r", stdin); // freopen("data1.out", "w", stdout);int T, Q;int ica = 1;scanf("%d", &T);init();while( T --){scanf("%d", &Q);int ans = bin(5, 5e8, Q);if(ans == -1) printf ("Case %d: impossible\n", ica ++);else printf("Case %d: %d\n", ica ++, ans);}return 0; }

C++版本三

題解：模擬一下牛頓迭代，那么可以使得復(fù)雜度變得更低。記get（x）為x！中零的個(gè)
數(shù)。那么答案必定在x~x-(k-get(x))之中。最后注意一下當(dāng)（k-get（x））小于10
的時(shí)候暴力一下。

///O(玄學(xué)) #include<bits/stdc++.h> using namespace std;int get(int x){int ret = 0;while(x){ret += x;x /= 5;}return ret; } int solve(int n){int x = n;while(true){int ret = get(x);if(abs(ret - n) <= 10){for(int i = min(n - ret, 0); i <= max(n - ret, 0); ++i){if(get(x + i) == n) return (x + i) * 5;}return -1;}x -= ret - n;}} int main() { // freopen("data1.in", "r", stdin); // freopen("check1.out", "w", stdout);int t;scanf("%d", &t);for(int cas = 1; cas <= t; ++cas){printf("Case %d: ", cas);int k;scanf("%d", &k);int ans = solve(k);if(ans == -1) puts("impossible");else printf("%d\n", ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Suffix Zeroes的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。