Trailing Zeroes (III)————二分+尺取练习

灰太狼 2022-05-17 19:56 239阅读 0赞

You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N!=1∗2∗...∗N  N ! = 1 ∗ 2 ∗ . . . ∗ N .  
For example, 5!=120,  5 ! = 120 ,  120 contains one zero on the trail.

**Input**  
Input starts with an integerT(≤10000)  T ( ≤ 10000 ) , denoting the number of test cases.

Each case contains an integer Q(1≤Q≤108)  Q ( 1 ≤ Q ≤ 10 8 )  in a line.

**Output**  
For each case, print the case number and N. If no solution is found then print ‘impossible’.

**Sample Input**  
3  
1  
2  
5  
**Sample Output**  
Case 1: 5  
Case 2: 10  
Case 3: impossible

--------------------

让你找阶乘末尾0个数是Q的数最小是多少，  
不存在的话就输出impossible  
关于阶乘末尾0的个数我这里有一篇博客讲怎么求：[n！末尾0的个数][n_0]

--------------------

具体看代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll MAXN=10000000000000;
    
    ll f(ll n)
    {
        ll ans=0;
        while(n)    ans+=(n/=5);
        return ans;
    }
    
    
    int main()
    {
        int t;ll Q;
        scanf("%d",&t);
        int kase=1;
        while(t--)
        {
            scanf("%lld",&Q);
            ll l=1,r=MAXN;
            ll ans=0;
            while(r>=l)
            {
                ll mid=(l+r)>>1;
                if(f(mid)==Q)
                {
                    ans=mid;
    //                break;//不能直接退出，因为阶乘末尾0个数等于Q的有很多呢，还得继续找最小的
                    r=mid-1;//
                }
                else if(f(mid)<Q)   l=mid+1;
                else                r=mid-1;
            }
            printf("Case %d: ",kase++);
            if(ans) printf("%lld\n",ans);
            else    printf("impossible\n");
        }
        return 0;
    }

[n_0]: https://blog.csdn.net/hpuer_random/article/details/79931500