|
试题 E: 求阶乘
时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分 【问题描述】 满足 N! 的末尾恰好有 K 个 0 的最小的 N 是多少? 如果这样的 N 不存在输出 −1。 【输入格式】 一个整数 K。 【输出格式】 一个整数代表答案。 【样例输入】 2 【样例输出】 10 【评测用例规模与约定】 对于 30% 的数据，1 ≤ K ≤ 10的6次方 对于 100% 的数据，1 ≤ K ≤ 10的18次方
这道题 我是学习了B站一个UP主，可以结合B站UP主的视频和我的这篇文章来学这道题。（这位B站UP主很厉害，但是我认为它的代码有一个地方可能需要修改）
十三届蓝桥杯javab组第二题第五题详解_哔哩哔哩_bilibili
//思路分析
//第1部分
//N的阶乘结果后边 有k个零
//写个方法long calc(long x) 计算x的阶乘后边有多少0
//突破口是 数字中谁和谁相乘得到10 没错就是2 和 5
//10的阶乘1*2*3*4* 5 *6* 7*8 *9*10
//10的阶乘1*2*3*2*2*5*2*3*7*2*4 *9*2*5 2个5
//2的个数肯定比5多
//所以N的阶乘最后有多少0 就看N能分成多少5 可以从1~N每个数都除以5，然后统计个数
//但是直接N/5 比如N为10时 10/5=2 1~10有2个5 分别是5和10包含5
// 再比如N为16时 16/5=3 1~16有3个5 分别是5和10和15包含5
//重点！！!! 当N为25时 25/5=5
// 1~25 = 1*2*..5*..*10*..*15*..*20*..25 这里25可以分成5*5
//也就是说N为25时 25的阶乘后边有6个0而不是5个0
//因为只除以一次5 发现25有两个5 125有3个5
//所以要循环除5！！！这里对照代码理解。
//第2部分
//因为k的值很大 不可能用枚举的思想依次对k比较
//我们先测一下 Long.MAX_VALUE的阶乘后边有多少个0
//Long.MAX_VALUE的阶乘后边有 2305843009213693937个0(10的19次方) > k
//Long.MAX_VALUE/2的阶乘后边有 1152921504606846964个0(10的19次方) > k
(所有在使用二分法时 有边界是Long.MAX_VALUE-5 左边界是1 不会有溢出)
//因为N的阶乘后边有k个0 这个k随N的增大而增大 所以我们用二分查找
//对于 100% 的数据，1 ≤ K ≤ 10的18次方
//把l = 1作为最左边 r = Long.MAX_VALUE - 5;做为最右边
//这里建议对照代码理解 如果不了解二分查找就看
//二分这段代码可以看B站UP主讲的
package lanqiao13;
import java.util.Scanner;
public class E {
// 求x的阶乘后边有多少个0
static long calc(long x){
long res = 0;
while (x!=0){
res = res+x/5;
x/=5;
}
return res;
}
//
static void solve() {
//第1部分代码
//System.out.print(calc(10));//计算10的阶乘是不是后边有2个0
//System.out.print(calc(25));//计算25的阶乘是不是后边有6个0
//第2部分代码
//System.out.print(calc(Long.MAX_VALUE/2 ));
//Long.MAX_VALUE的阶乘后边有 2305843009213693937个0
//Long.MAX_VALUE/2的阶乘后边有 1152921504606846964个0
//二分查找
Scanner scanner = new Scanner(System.in);
long k = scanner.nextLong();
long l = 1, r = Long.MAX_VALUE - 5;//l为最左边 r为最右边
//long l = 1, r = 20;//方便学习可以debug
while (l < r) {
long mid = (l + r) / 2;
if (k |