G - G 使用long long
Time Limit:
2000
MS
Memory Limit:
32768
KB
64bit IO Format:
%lld & %llu
Submit Status Practice LightOJ 1138 uDebug
Description
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
题意：
让你求一个最小的n，使得n的阶乘含有q个0；
思路：任意一个数都可以写成质因数的幂的乘积，n=2^a*5^b*……；其中2的幂数肯定比5的多，而0的产生是有2*5；
所以5的个数决定了0的个数；有多少个0就要有多少个5；所以问题转化为求n中5的个数；
5！~1 10！~2 15！~3 20! ~4 25! ~6 30! ~7;
然后二分查找n,记得右区间要开大点；
代码：
#include<stdio.h>
#include<string.h>
long long judge(long long mid)//求n中含有的5的个数；
{long long ans=0;while(mid){ans+=mid/5;mid/=5;}return ans;
}
int main()
{int t,q,mm=1;scanf("%d",&t);while(t--){scanf("%d",&q);long long l=0,r=5000000000;long long sum=0;bool flag=0;while(l<=r){long long mid=(l+r)/2;if(judge(mid)==q){sum=mid;r=mid-1;//因为要找最小的n,所以满足题意之后仍然要往左找； flag=1;}else if(judge(mid)>q){r=mid-1;}else{l=mid+1;}}if(flag)printf("Case %d: %lld\n",mm++,sum);elseprintf("Case %d: impossible\n",mm++);}return 0;
}