（Java）题解 2674: 蓝桥杯2022年第十三届省赛真题-求阶乘

CSDN链接，有什么问题可以来私信一起讨论，加油

package LanqiaobeiExam._13JB;
import java.util.Scanner;
/**
 * ClassName: 求阶乘
 * Package: LanqiaobeiExam._13JB
 *
 * @DATE: 2022/5/15 14:34
 * Author: asleep
 */
public class 求阶乘 {
    /*
    *   0的数量只和 2 5相关，在结成中每遇到一个 5 肯定遇到两个或者多个 2 （10其实就是2*5构成的，无需单独考虑）
    *   因此只需要记录5的数量即可
    *
    *   ！！！错误方向：我们发现25是两个五，得出6个五为一组，然后推出结论，
    *   ！！！错误原因：25是两个五，等到125就是三个五，625就是四个五，无法分为具体几个一组（很多人都没向后想）
    *       我还记得当时我分享解题思路的时候，有个博主和我说没必要，动态规划即可，六个一组就行，狗头保命
    *       这里并不是说什么对错，而是对于一个题如果有讨论有争议，等学会以后你会对这个题印象更加深刻，多交流，加油
    *
    *   正确方向：25是有2个5，125是3个5，问题是怎么确定有几个25，几个125呢
    *           我们假设n个0，n/5就是有多少个5，
    *           n/25是有多少个25，25里面有两个5，但是我们/5的时候其实一个5已经被计算好了
    *               所以我们只需要计算n/25就行了，
    *           n/125同理，125是3个5，我们/5和/25的时候计算了当前125的2个5，n/125即可计算出最后一个5
    *           …………
    *           大家可以拿个笔，拿个纸画一画
    *
    *           现在我们可以根据n个0求出来这个数是多少
    *           我们二分这个数字，然后检查他是否有n个0，
    *           如果二分出来的数字，并没有n个0，则证明当前n不存在对应的数字
    */
    //先把5的n次方求出来，因为数据范围为1e18，只需要找到长度为18的数字即可（记得用long）
    static long[] num = {5L, 25L, 125L, 625L, 3125L, 15625L, 78125L, 390625L, 1953125L, 9765625L, 48828125L, 244140625L, 1220703125L, 6103515625L, 30517578125L, 152587890625L, 762939453125L, 3814697265625L, 19073486328125L, 95367431640625L, 476837158203125L, 2384185791015625L, 11920928955078125L, 59604644775390625L, 298023223876953125L, 1490116119384765625L, 7450580596923828125L};
    public static void main(String[] args) {
//        long temp = 1L;
//        for (long i = 1L; i <= 50; i++) {
//              temp *= 5;
//            System.out.print(temp + "L, ");
//        }
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long left = 0L, right = (long) 9e18;    //二分范围
        while (left < right) {  //二分目标值
            long mid = (left + right) / 2;
            if (check(mid) < n) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (check(right) == n) {    //如果二分出来的结果不符合，则输出-1
                System.out.println(right);
        } else {
            System.out.println(-1);
        }
    }
    public static long check(long n) {
        long res = 0L;
        for (int i = 0; i < num.length; i++) {
            res += n / num[i];
        }
        return res;
    }
}