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
这道题 想了 好长时间 ，到最后 答案是 算出来啦 但是 不是超时， 就是 memery 超啦，唉。。。 不过 最终 还是 会写啦 。先说一下 题目的 大意，就是 给你一个 数 表示 某个数 N 结成后 得到的 值的 后面 number of all behand zero, 就是 末尾 零的个数， 然后 让你写一个 程序 给你 零的 个数 然后 输出 那个 数 。 了解题目的大意之后 简单的 思考一下 感觉 题目的意思 不是很难， 但是 请仔细的看一下数据的范围 ，给的 时间的 2 秒，如果 用 一般的方法写的话 一定会超时 的 ，或者 内存超限，简单的思考一下 ，乘法可以得到零的 只有 偶数 和 5 相乘 然而 n！ 之中 偶数的个数 显然是 多的 用不完 啦 ，那么 零的 个数 就是 与 5 的个数 有关 啦， 而且 一个5 只能得到 一个零 ， 所以 零的 个数 = N！中 5 的个数，好啦 现在 的问题就是 找 一个数 n 含有 几个5 啦。下面程序里 有一个函数 ，是 求解 一个数 对应 阶乘 数 中 零的 个数 ， 原理 大概说一下 ： 他是 先找 n！ 中 1 =》 n 中 可以 被 5 整除的 数的 个数 ，然后 在 计算 可以 被 5*5 整除的数的 个数 ，保证 除数 不大于 被除数 N ， 最后 将 找的的 个数 累加 起来 就是 对应 零的 个数 啦 列一个 例子： n = 100；
1 =》 100 中 可以 被 5 整除的 有 5，10，15，……，85， 90， 95， 100， 能够 被 5*5 整除的 数 为： 25， 50， 75， 100， 所以 100！ 中 末尾 零的 个数 为 20 + 4 = 24 个； 这其中 为了 减少时间 ，没有 用 循环 而是用的 线段树 相当于 二分 法查找 ，找出 答案 ；具体过程 看 下面的代码；
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;
long long n;
long long get_5(long long n)
{ long long ans=0; long long five=5; while(n>=five) { ans+=n/five; five*=5; } return ans;
}
long long solve(long long l,long long r)
{ long long mid=(l+r)/2; long long tmp=get_5(mid); if(l==r) { if(get_5(mid)==n) return mid; else return -1; } if(tmp<n) { return solve(mid+1,r); } else if(tmp>n) { return solve(l,mid); } else return mid; }
int main()
{ int t; scanf("%d",&t); for(int cases=1;cases<=t;cases++) { scanf("%lld",&n); long long ans=solve(0,1000000000000); if(ans==-1) printf("Case %d: impossible\n",cases); else { while(get_5(ans-1)==n) // 题目要求 最小的 数ans--; printf("Case %d: %lld\n",cases,ans); } } return 0;
}