lightoj1138数学—数学小知识点-蒲公英云

lightoj1138数学—数学小知识点

G - G 使用long long

Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu

Submit Status Practice LightOJ 1138 uDebug

Description

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. For example, 5! = 120, 120 contains one zero on the trail.

Input

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

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

Output

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

Sample Input

Sample Output

Case 1: 5

Case 2: 10

Case 3: impossible

n！末尾0的个数实际上就是求5在整个式子中能得到的个数。例如10！末尾有两个0，那么1*2*3*4*5*6*7*8*9*10=1*2*3*2*2*5*2*3*7*2*2*2*9*5*2 。任何两个一位数相乘只有2*5等于10，贡献一个0,显然2的个数是要比5多的，所以求5的个数就行了。这个过程的代码：

LL get(LL x) {
    LL ans=0;
    while(x) {
        ans+=x/5;
        x=x/5;
    }
    return ans;
}

ac代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#define LL long long
#include<algorithm>
using namespace std;
LL judge(LL mid) {
    LL count=0;
    while(mid) {
        count+=mid/5;
        mid=mid/5;
    }
    return count;
}
int main() {
    int T,p=0;
    scanf("%d",&T);
    while(T--) {
        LL Q;
        scanf("%lld",&Q);
        LL left=1,right=1e18;
        LL mid;
        LL ans=0;
        while(left<=right) {
            mid=left+right>>1;
            if(judge(mid)>Q) {
                right=mid-1;
            } else if(judge(mid)<Q) {
                left=mid+1;
            } else{
                ans=mid;
                right=mid-1;
            }
        }
        if(ans)
            printf("Case %d: %lld\n",++p,ans);
        else
            printf("Case %d: impossible\n",++p);
    }
    return 0;
}