vjudge Trailing Zeroes (III) （二分答案 数论）

嗯...

 

题目链接：https://vjudge.net/contest/318956#problem/E

 

这道题是二分答案+数论，但首先是数论，否则你不知如何二分...

 

首先关于一个阶乘的结果最后会出现0（即10），肯定是由2 * 5所造成的，而对于正整数 N，在[0, N]范围内，质因子中含有 2 的总是会比质因子含有 5 的要多。所以，只要需要知道质因数含有 5 的数字有多少个，即可知道末尾连续出现 0 的个数有多少...

 

然后我们进行二分答案，从1~5e8 + 5（一定要足够大！）进行二分，如果当前答案处理出来的5的个数正好等于a，那么它可能是答案，因为可能我们把较小的遗漏了，所以我们要继续二分，如果有比它小的，继续更新...

 

AC代码：

#include<cstdio>
#include<iostream>

using namespace std;

inline int check(int x){
    int ans = 0;
    while(x){
        ans += x / 5;
        x /= 5;
    }
    return ans;
}//处理5的个数，即末尾0的个数 

int main(){
    int t, m = 0;
    scanf("%d", &t);
    while(t--){
        int ans = 0, a;
        m++;
        scanf("%d", &a);
        int l = 1, r = 5e8 + 5;
        while(l <= r){
            int mid = (l + r) >> 1;
            int _mid = check(mid);
            if(_mid > a) r = mid - 1;
            else if(_mid < a) l = mid + 1;
            else if(_mid == a) {ans = mid; r = mid - 1;}//可能有答案遗漏 
        }
        if(ans) printf("Case %d: %d\n", m, ans);
        else printf("Case %d: impossible\n", m);
    }
    return 0;
}