首页 > 代码库 > LightOJ Trailing Zeroes (III) 1138【二分搜索+阶乘分解】
LightOJ Trailing Zeroes (III) 1138【二分搜索+阶乘分解】
1138 - Trailing Zeroes (III)
PDF (English) | Statistics | Forum |
Time Limit: 2 second(s) | Memory Limit: 32 MB |
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 |
Output for Sample Input |
3 1 2 5 |
Case 1: 5 Case 2: 10 Case 3: impossible |
PROBLEM SETTER: JANE ALAM JAN
题意:给你一个数字,这个数字代表N!后面有几个0。给出这个数字,计算N的值。
解题思路:
不论什么质因数都能够写成素数相乘的形式。所以计算一个数的阶乘后面几个0。仅仅需计算这个数包括多少5就可以。(关于这点不清楚的点:点击打开链接)。
能够用二分法,找出这个点。
想到用二分这道题也就没什么难度了。
AC代码;
<span style="font-size:18px;">#include <stdio.h> #include <math.h> #include <vector> #include <queue> #include <string> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; LL solve(LL n) { LL num=0; while(n){ num+=n/5; n/=5; } return num; } LL er(LL n) { LL x=1; LL y=1844674407370; LL mid; LL res=-1; while(y>=x){ mid=(x+y)/2; LL ans=solve(mid); if(ans==n){ res=mid; y=mid-1; //return mid; } else if(ans>n){ y=mid-1; } else if(ans<n){ x=mid+1; } } return res; } int main() { int t; scanf("%d",&t); int xp=1; while(t--){ LL n; scanf("%lld",&n); LL ans=er(n); if(ans==-1) printf("Case %d: impossible\n",xp++); else printf("Case %d: %d\n",xp++,ans); } return 0; } </span>
LightOJ Trailing Zeroes (III) 1138【二分搜索+阶乘分解】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。