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
3
1
2
5
Sample Output
Case 1: 5
Case 2: 10
Case 3: impossible
思路：
有几个零就是看能分解出几个5，所以用二分查找是否存在能分解出n个5的数
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<queue>
#include<cmath>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define ll long long
const int N=1e5+5;
const int MOD=1000;
const double C=0.57721566490153286060651209;
using namespace std;
ll judge(int x){ //判断数x能分解出5的个数
ll res=0;
while(x){
res+=x/5;
x/=5;
}
return res;
}
ll panduan(ll n){
ll l=0,r=5e8+1;
ll mid,res;
while(r>=l){
mid=(l+r)/2;
if(judge(mid)>=n){
res=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
return res;
}
int main(){
int T,num=1;
ll ans,n;
ll mid,l,r;
scanf("%d",&T);
while(T--){
scanf("%lld",&n);
int ans=panduan(n);
if(judge(ans)==n){
printf("Case %d: %lld\n",num++,ans);
}
else{
printf("Case %d: impossible\n",num++);
}
}
return 0;
}