LIGHT OJ 1138 - Trailing Zeroes (III)【N!后0的个数&&二分（好题）】

1138 - Trailing Zeroes (III)

PDF (English)

Statistics

Forum

Time Limit: 2 second(s)

Memory Limit: 32 MB

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 ≤ 10⁸) in a line.

Output

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

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

 

---

PROBLEM SETTER: JANE ALAM JAN

随着N的增大 0的个数非递减 二分枚举判断即可

代码中统计N!中5的个数依然可以用于统计>1的任何整数；

AC代码：

#include<cstdio>

typedef long long LL;
const LL INF=1e18;

LL Sum(LL N) {//N!后0的个数即统计N!能除以多少个5 直接统计1-N中5的倍数 
LL ret=0; //考虑到1-N中有可能含有5的次方 所以缩小5倍之后继续统计 
while(N) { //即依次统计能被5^1整除的个数 5^2整除的个数 5^3 .....
N/=5; ret+=N;
}
return ret;
}
int main() {
LL T,Kase=0; scanf("%lld",&T);
while(T--) {
LL Q; scanf("%lld",&Q);
    LL R=INF,L=1,ans=INF;
    while(L<=R) {
    LL mid=L+R>>1;
        LL s=Sum(mid);
        if(s==Q) {
        ans=mid;R=mid-1;
}
else if(s>Q) R=mid-1;
else L=mid+1;
}
printf("Case %d: ",++Kase);
if(ans>=INF)  puts("impossible");
else printf("%lld\n",ans);
} 
return 0;
}