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 knowN! = 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.
OutputFor each case, print the case number and N. If no solution is found then print'impossible'.
Sample Input3
1
2
5
Sample OutputCase 1: 5
Case 2: 10
Case 3: impossible
阶乘末尾包含多少个0,那么n以内的数的乘积就包含了多少个10,等价于包含了多少个5,例25的阶乘:25有两个5,20,15,10,5各包含1个5,共6个5,所以25以内有6个5,所以25!有6个0;
(要直接找10的个数是不行的,因为有很多的10是5的倍数乘以偶数形成的,实质上还是5的个数,并且5的倍数肯定比2的倍数少,只要有5就肯定有2让他两形成10)
给你一个零的个数n,用二分找m使得m!的0的个数为n个,找最小的m
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
const LL MAXN=((LL)1<<32);
#define fi first
#define se second
int main()
{
int T,cas=0;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
int left=1,right=5*n+10,mid=(left+right)/2;
while(left<right)
{
mid=(left+right)/2;
int z=0,h=mid;
while(h)
{
z+=h/5;
h/=5;
}//m以内5的个数
if(z<n)left=mid+1;
else if(z>n)right=mid;
else break;
}
mid=(mid/5)*5;
int z=0,h=mid;
while(h)
{
z+=h/5;
h/=5;
}
printf("Case %d: ",++cas);
if(z!=n)puts("impossible");
else printf("%d\n",mid);
//printf("%d\n",mid);
}
return 0;
}
上一篇: 线程学习1.1
下一篇: redis集群常见问题合集
推荐阅读
-
LightOJ - 1138
-
1138 Postorder Traversal
-
1138 Postorder Traversal
-
【代码超详解】LightOJ 1259 Goldbach`s Conjecture(欧拉筛)
-
1138:将字符串中的小写字母转换成大写字母
-
LightOJ - 1282(n^k的前三位数字和后三位数字)
-
巧用TreeSet求解第k小整数(洛谷P1138题题解,Java语言描述)
-
lightoj1265 Island of Survival(思维或dp)
-
Consistency Checker LightOJ - 1129
-
Consistency Checker LightOJ - 1129