Suffix Zeroes

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

C++版本一

题解：这个题让我想起了https://codeforces.com/contest/837/problem/D

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

思路差不多，因为这个题5肯定比2少所以只要考虑5就行

不过我考虑了二分答案和每个数字前面5出现的情况所以感觉还行

就是内存有点多，时间有点长

/*
*@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 DEBUG

using 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 DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%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，若将阶乘中所有的数拆分成质因子的乘积，发现只有2*5 才能产生
0，同时2 会比5 的个数多。故直接二分n，check 5 的个数。

#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++版本三

题解：模拟一下牛顿迭代，那么可以使得复杂度变得更低。记get（x）为x！中零的个
数。那么答案必定在x~x-(k-get(x))之中。最后注意一下当（k-get（x））小于10
的时候暴力一下。

///O(玄学)
#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;
}