试题 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 <= calc(mid)) {//如果mid的阶乘的0数大于等于k                r = mid;//我们让r变为mid (可以等于mid)            } else {//如果mid的阶乘的0数小于k                l = mid + 1; //我们让l变为mid+1(大于mid,所以可以+1)                //并且这里想让while循环中止就要不得不+1            }        }        //二分法 l是最后的答案         if (calc(r) != k) {            System.out.println(-1);        } else {            System.out.println(r);        }    }    public static void main(String[] args) throws Exception{        //System.out.println((Long.MAX_VALUE + 1)/2);        // 大于Long.MAX_VALUE 会变成负数 所以有必要改进        solve();    }}

    //另外二分查找比较薄弱的可以看B站韩顺平老师讲的  “韩顺平老师YYDS！”

韩老师讲的二分查找地址：【尚硅谷】数据结构与算法（Java数据结构与算法）_哔哩哔哩_bilibili

谢谢观看！这道题对我来说太难了！！！