Light oj 1138 - Trailing Zeroes (III) 【二分查找好题】【 给出N!末尾有连续的Q个0,让你求最小的N】
查找 最小 二分 连续 III OJ 给出 Light
2023-09-11 14:14:43 时间
1138 - Trailing Zeroes (III)
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
题意:给你一个数Q。代表N!中 末尾连续0的个数。让你求出最小的N。
定理:求N!
中 末尾连续0的个数
求法例如以下
LL sum(LL N) { LL ans = 0; while(N) { ans += N / 5; N /= 5; } return ans; }
又犯二了,区间开小了。
WA了一次。
AC代码:用二分实现的
#include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <queue> #include <stack> #include <vector> #include <map> #include <string> #include <algorithm> #define LL long long #define MAXN 100+10 #define MAXM 20000+10 #define INF 0x3f3f3f3f using namespace std; LL sum(LL N)//求N阶乘中 末尾连续的0的个数 { LL ans = 0; while(N) { ans += N / 5; N /= 5; } return ans; } int k = 1; int main() { int t; LL Q; scanf("%d", &t); while(t--) { scanf("%lld", &Q); LL left = 1, right = 1000000000000;//一開始开小了 醉了 LL ans = 0; while(right >= left) { int mid = (left + right) >> 1; if(sum(mid) == Q)//相等时 要赋值给ans { ans = mid; right = mid - 1; } else if(sum(mid) > Q) right = mid - 1; else left = mid + 1; } printf("Case %d: ", k++); if(ans) printf("%lld\n", ans); else printf("impossible\n"); } return 0; }
相关文章
- L18 如何快速查找文档获得帮助
- Java实现 LeetCode 373 查找和最小的K对数字
- 数组查找的时间复杂度正确表述
- 数据结构和算法-查找算法-树和二叉树查找
- linux根据进程号PID查找启动程序的全路径
- linux下查找java进程占用CPU过高原因
- Python语言学习:在python中,如何获取变量的本身字符串名字而非其值/内容及其应用(在代码中如何查找同值的所有变量名)
- 719. 找出第 K 小的数对距离-二分查找
- 【算法】测试1 查找
- 【算法图文动画详解系列】KMP 字符串查找算法(Knuth-Morris-Pratt )
- Linux下如何查找可执行文件
- 在查找预编译头时遇到意外的文件结尾。是否忘记了向源中添加“#include "StdAfx.h"”?