light oj 1138

Trailing Zeroes (III)

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

Submit Status

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 ≤ 10⁸) 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

Source

Problem Setter: Jane Alam Jan

数论！！！加二分....

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <math.h>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <climits>
 8 #include <queue>
 9 #define ll long long
10 
11 
12 using namespace std;
13 ll ans;
14 ll zero(ll num)
15 {
16     ll i,sum = 0;
17     for(i = 5; i <= num; i *= 5)
18         sum += num/i;
19     return sum;
20 }
21 void check(int n)
22 {
23     ll low = 5,mid,high;
24     high = 0x3f3f3f3f3f;
25     while(low <= high)
26     {
27         mid = (low+high)/2;
28         ll temp = zero(mid);
29          if(n < temp)
30             high = mid-1;
31         else if(n > temp)
32             low = mid+1;
33         else if(n == temp)
34         {
35             if(mid == low)
36             {
37                 ans = mid;
38                 return;
39             }
40             high = mid;
41         }
42     }
43 }
44 
45 int main(void)
46 {
47     int t,n,cnt = 1;
48     cin>>t;
49     while(t--)
50     {
51         scanf("%d",&n);
52         ans = -1;
53         check(n);
54         if(ans == -1)
55             printf("Case %d: impossible
",cnt++);
56         else
57             printf("Case %d: %lld
",cnt++,ans);
58     }
59     return 0;
60 }