Trailing Zeroes (III) LightOJ - 1138(二分)

时间:2022-09-12 20:19:29

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

转一下题解:原文地址:https://blog.csdn.net/zs120197/article/details/52244482

不难发现,一个数一共包含了几个5,就会有几个零;比如,

5以及5之前的数一共包含了1个5,所以末尾共有1个零;

20以及20之前的数一共包含了4个5(5自身为1个,10包含一个,15包含一个,20包含一个),所以末尾共有4个零;

25以及25之前的数一共包含了6个5(5,10各包含一个,15包含一个,20包含一个,25包含另个(5*5等于25,所以25包含两个)),所以末尾共有6个零;

28以及28之前的数一共包含了6个5,所以末尾共有6个零;

……
这样,我们只需要求出所要求的数n一共包含了几个5,然后在从0-500000000(因为Q最大是100000000,所以要查找的范围上限最大是500000000)中查找是否有一个数它所包含的5的个数等于n就行了,如果有等于n,那么输出查找到的这个数,如果没有,则输出不可能;
注意这里要用二分查找会减少时间复杂度避免超时;

代码如下:

题中要求的是最小的N 所以注意二分的范围问题。。。

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define maxn 100009
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int LL_INF = 0x7fffffffffffffff,INF = 0x3f3f3f3f; LL init(LL x)
{
int cnt = ;
while(x)
{
cnt += x / ;
x /= ;
}
return cnt;
} LL check(LL Q)
{
LL x = , y = ;
while(x <= y)
{
LL m = x + (y-x)/;
int ans = init(m);
if(Q <= ans) y = m-;
else x = m+;
}
if(init(x) == Q) return x;
return ;
} int main()
{
int T, kase = ;
cin>> T;
while(T--)
{
LL Q;
cin>> Q;
int ix = check(Q);
if(ix)
printf("Case %d: %d\n",++kase,ix);
else
printf("Case %d: impossible\n",++kase); } return ;
}