b: Suffix Zeroes
Time Limit: 1 Sec Memory Limit: 128 MB
Description
这个游戏超休闲的~。现在你需要找一个自然数n，你找的自然数需要满足n!的末尾恰好有k个0（当然我们都是十进制下的数，n! = 1*2*3*…*n）。比如：5！= 120，尾部恰好有一个0。
Input
先输入T，代表有T组数据（T ≤10000）接下来的T行每一行都包括一个数字k（1≤k≤108）。具体含义请见题意。
Output
如果能找到这样的数，请输出满足条件的最小的自然数n，如果不存在这样的自然数，请输出impossible。
Sample Input
2
1
5
Sample Output
Case 1: 5
Case 2: impossible
我们发现末尾有一个0就代表有一个因数10，那么有多少个0就可以分解出多少个10，而10=2*5，显然当n>=5时，n!中可以分解出的2的数量是比5多的，所以这题就变成求n！能分解出多少个5。通过找规律很容易发现，能分解出5的数量为n/5+n/(5^2)+n/(5^3)+……,因此容易证明答案不超过5e8,直接二分答案即可。
1 #include<cstdio>
2 #include<algorithm>
3 using namespace std;
4 #define rd(a) scanf("%d",&a)
5 #define rep(i,a,b) for(int i=(a);i<=(b);i++)
6 int calc(
int x){
7 int cnt=
0;
8 int a=
5;
9 while(x>=
a){
10 cnt+=x/
a;
11 a*=
5;
12 }
13 return cnt;
14 }
15 int main(){
16 int T;
17 rd(T);
18 rep(tt,
1,T){
19 int k;
20 rd(k);
21 int L=
1,R=
5e8;
22 while(R-L>
1){
23 int mid=L+R>>
1;
24 if(calc(mid)>=k)R=
mid;
25 else L=
mid;
26 }
27 printf(
"Case %d: ",tt);
28 if(calc(R)==k)printf(
"%d\n",R);
29 else puts(
"impossible");
30 }
31 }
View Code
转载于:https://www.cnblogs.com/KafuuMegumi/p/10090773.html
