LightOJ - 1138 Trailing Zeroes (III)

Trailing Zeroes (III)

  LightOJ - 1138 

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.

大体题意：N！后面有Q个0，给你Q,求N

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

思路：

实际N!后面有几个0的问题可以转化位N!里有几个10,2*5=10，2的个数显然大于5的个数(想到这个就简单了)，于是我们统计5的个数，再利用二分查找

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

ll sum(ll n) {
    ll cnt = 0;
    
    while(n) {
        cnt += n/5;
        n /= 5;
    }
    
    return cnt;
}

ll bin_search(int t) {
    ll left = 1;
    ll right = 500000000;
    ll res = -1;
    
    while(left <= right) {
        ll mid = (left+right) / 2;
        ll cnt = sum(mid);
        if(t == cnt) {
            res = mid;
            right = mid - 1;
        } else if(cnt < t) {
            left = mid + 1;
        } else if(cnt > t) {
            right = mid - 1;
        }
    }
    
    return res;
}

int main() {
    int n;
    
    cin >> n;
    
    for(int i = 1;i <= n;i++) {
        int t;
        cin >> t;
        ll flag = bin_search(t);
        
        if(flag == -1) {
            printf("Case %d: impossible\n",i);  
        }
        else { 
            printf("Case %d: %lld\n",i,flag);
        }
    }
    
    return 0;
}