lightoj1138数学—数学小知识点

浅浅的花香味﹌ 2022-07-17 00:27 151阅读 0赞

G - G 使用long long

**Time Limit:**2000MS **Memory Limit:**32768KB **64bit IO Format:**%lld & %llu

Submit [Status][] [Practice][] [LightOJ 1138][] [![12x12_uDebug.png][]uDebug][12x12_uDebug.png_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

Sample Output

Case 1: 5

Case 2: 10

Case 3: impossible

n！末尾0的个数实际上就是求5在整个式子中能得到的个数。例如10！末尾有两个0，那么1\*2\*3\*4\*5\*6\*7\*8\*9\*10=1\*2\*3\*2\*2\*5\*2\*3\*7\*2\*2\*2\*9\*5\*2 。任何两个一位数相乘只有2\*5等于10，贡献一个0,显然2的个数是要比5多的，所以求5的个数就行了。这个过程的代码：

LL get(LL x) {
    	LL ans=0;
    	while(x) {
    		ans+=x/5;
    		x=x/5;
    	}
    	return ans;
    }

ac代码：

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #define LL long long
    #include<algorithm>
    using namespace std;
    LL judge(LL mid) {
    	LL count=0;
    	while(mid) {
    		count+=mid/5;
    		mid=mid/5;
    	}
    	return count;
    }
    int main() {
    	int T,p=0;
    	scanf("%d",&T);
    	while(T--) {
    		LL Q;
    		scanf("%lld",&Q);
    		LL left=1,right=1e18;
    		LL mid;
    		LL ans=0;
    		while(left<=right) {
    			mid=left+right>>1;
    			if(judge(mid)>Q) {
    				right=mid-1;
    			} else if(judge(mid)<Q) {
    				left=mid+1;
    			} else{
    				ans=mid;
    				right=mid-1;
    			}
    		}
    		if(ans)
    			printf("Case %d: %lld\n",++p,ans);
    		else
    			printf("Case %d: impossible\n",++p);
    	}
    	return 0;
    }

[Status]: http://acm.hust.edu.cn/vjudge/contest/129616#status//G/0
[Practice]: http://acm.hust.edu.cn/vjudge/problem/26852
[LightOJ 1138]: http://acm.hust.edu.cn/vjudge/problem/26852/origin
[12x12_uDebug.png]: http://acm.hust.edu.cn/vjudge/images/12x12_uDebug.png
[12x12_uDebug.png_uDebug]: https://www.udebug.com/LOJ/1138