首页 > 代码库 > LightOj 1138 - Trailing Zeroes (III) 阶乘末尾0的个数 & 二分
LightOj 1138 - Trailing Zeroes (III) 阶乘末尾0的个数 & 二分
题目链接：http://lightoj.com/volume_showproblem.php?problem=1138
题意：给你一个数n，然后找个一个最小的数x，使得x!的末尾有n个0；如果没有输出impossible
可以用二分求结果，重点是求一个数的阶乘中末尾含有0的个数，一定和因子5和2的个数有关，因子为2的明显比5多，所以我们只需要求一个数的阶乘的因子中一共有多少个5即可;
LL Find(LL x){ LL ans = 0; while(x) { ans += x/5; x /= 5; } return ans;}
例如125! 125/5 = 25；所以125!中含5的项为25*5+24*5+23*5+...+3*5+2*5+1*5 = 25!*5
所以125!末尾有25+5+1 = 31 个0;
#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>typedef long long LL;#define N 1000001using namespace std;const double eps = 1e-6;LL Find(LL x){ LL ans = 0; while(x) { ans += x/5; x /= 5; } return ans;}int main(){ int T, t = 1, n; scanf("%d", &T); while(T --) { scanf("%d", &n); LL ans = 0, L = 2, R = 1000000000; while(L <= R) { LL Mid = (L+R)/2; LL ret = Find(Mid); if(ret == n) ans = Mid; if(ret >= n) R = Mid - 1; else L = Mid + 1; } if(ans == 0) printf("Case %d: impossible\n", t++); else printf("Case %d: %lld\n", t++, ans); } return 0;}
LightOj 1138 - Trailing Zeroes (III) 阶乘末尾0的个数 & 二分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。