LightOJ 1138 Trailing Zeroes (III)

题目链接:点我

题目

---

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

---

题意:

求是否存在一个数,它的阶乘末尾有q个0.

思路:

我们知道,在n!中,每一个末尾0都是由2 和 5 贡献的,那么我们只需要知道前n个数中有多少对2 和5即可,然后我们发现,5的数量比2 会少很多,所以,我们只需要知道有多少个5就可以了,然后我们直接在所有可能的n中进行二分即可

代码:

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;

typedef long long LL;
LL sum(LL n){
    LL ans = 0;
    while(n){
        ans += n / 5;
        n /= 5;
    }
    return ans;
}

int main(){
    int t;
    scanf("%d", &t);
    int kase = 0;
    while( t--){
        int n;
        scanf("%d", &n);
        LL l = 0;
        LL r = 10000000000000;
        while( l <= r){
            LL mid = (l + r) >> 1;
            if(sum(mid) >= n) r = mid -1;
            else l = mid + 1;
        }
        printf("Case %d: ",++kase );
        if(sum(l) == n)
            printf("%lld\n",l);
        else printf("impossible\n");
    }
    return 0;
}