题目

满足 N!的末尾恰好有 K个 0的最小的 N是多少?

如果这样的 N，不存在输出 −1

输入格式

一个整数 K

输出格式

一个整数代表答案。

数据范围

对于 30%的数据，1≤K≤10⁶
对于 100%的数据，1≤K≤10¹⁸

测试地址：官方测试地址

思路

对于末尾有多少0，这个问题可以转化为在阶乘的所有相乘的项内，能转化出多少10，比如

5！ = 5 * 4 * 3 * 2 * 1 = ( 2 * 5 )* 3 * 1 * 4 = 10 * 3 * 4 * 1 = 120.

10! = 10 * 9 * 8 * 7 * 6 * 5 * 5 * 4 * 3 * 2 * 1 = 10 * 5 * 2 * …… = 3628800

我们接着可以得到阶乘各项中10的个数与5密切相关，因为偶数的数目一定比5多，任何一个5的幂次倍都可以乘以一个指定的偶数变为10的幂次倍。

简单来说就是

5 * 2 = 10 = 10¹

25 * 4 = 100 = 10²

125 * 8 = 1000 = 10³

那非5的幂次倍的，但是它是5的倍数可不可以分出10来呢？，比如15 = 5 *3 ，只需要再来一个任意的偶数分出的2就可以分出一个10。

那么现在就知道是0的个数就是阶乘中每一项能分出的5的个数。

这个个数该如何计算呢？

你现在已知的是有最后有几个0，也就是阶乘各项分解之后有几个5.

数	5	10	15	20	25	30	35	…	125	…	175	200	…	625
可分出的5的个数	1	1	1	1	2	1	1	…	3	…	2	2	…	4

通过上表可以看出5的幂次倍可以分出相应次数个5，而5 的倍数能分出的5的个数就取决于它是单是5 的倍数还是也是5的幂次方的倍数。

但我们应该如何去计算这个5的个数呢？

我们可以看出，10 - 25一共可以提取出5个5，这个5正好是25/5

30 - 125 一共可以提取25个5（可以看这个Excel表），这个正好也是125/5 = 25

那么对于5的总数就可以All = N / 5 + N / 25 + N / 125 + N / 5ⁱ

对于这样的话，我们可以根据给出的数据范围去判断一下最大的5ⁱ是多少，并将它放到一个long的数组内，对于这个我们最好是数组准备的大一些，但是1e19甚至会超过long的最大值，所以可以用2e18。

    public static void get(){
        System.out.print("{");
        long i=5;
        while (i<2e18){
            System.out.print(i+"L,");
            i*=5;
        }
        System.out.print("}");
    }

得到以下数组

    long[] arr = {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};

那么对于任何一个数都可以计算出可以提取出多少5，也就可以判断末尾有多少0

    public static long getZero(int n){
        long ans = 0L;
        for (long l : arr) {//arr就是上面的arr，为了这里使用，需要将arr定义为类变量，并且静态
            ans += n / l;
        }
        return ans;
    }

这里其实在本地就可以暴力去循环得到指定的答案

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long k = scanner.nextLong();
        long i = 5;
        while (true){
            long num = getZero(i);
            if (num == k) {
                System.out.println(i);
                break;
            }else if (num<k){
                i++;
            }else {
                System.out.println(-1);
                break;
            }
        }
    }

很好理解从5开始是末尾一个0，之后依次每个判断，直到得到正确结果或者以已经超过指定的K就可以break，这样的复杂度看似也只有O（N）但是要注意的是，这个N太大了，数据范围K要达到10的18次方。

因此我们可以用一下二分查找

二分查找

既然要二分那么就需要一个范围，左边界一定就是5，那么这个最大值应该是多少呢？

最大的应该是要阶乘的结果比末尾10的18次方颗0大的多的那个数，但是说实在的，谁也不知道那是个啥数，所以索性就先使用long的最大值

long L = 5L；
long R = Long.MAX_VALUE;

然后就是很平常的二分过程

二分的标志是该数的getZero()

如果少于要求的k值，那么这个数还不够大，就只要左半部分。也就是将有边界设置为mid

如果大于k值，那么这个数还不够小，要将左边界设为mid+1

while (L < R){
    long mid = (L+R)/2;
    if (getZero(mid) < k){
        L = mid+1;
    }else {
        R = mid;
    }
}

查找到最后的结束就是一个L=R。

这个就是最后的可能结果

这时需要再进行一次判断

if (getZero(R) == k){
    System.out.println(R);
}else {
    System.out.println(-1);
}

那么这就是全部的思路了。

但是这个最大的右值依然有问题

假如我们去提交呢

假如我们输入指定的数据范围的最大值10¹⁸，我们会发现很久都没有结果，那么我们就可以自己去减小范围，可以用下面这个来计算一下时间

long start =System.currentTimeMillis();
…………
…………
long end = System.currentTimeMillis();
System.out.println(end-start);

减小范围可以先直接用这个最大值减一个数去尝试

在最大值减去5的时候就出现了1ms出结果的情况，虽然不清楚是啥情况，但是现在就可以100%通过测试

完整代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static long[] arr = {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};
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //long start =System.currentTimeMillis();
        long k = scanner.nextLong();
        long L = 5L;
        long R = Long.MAX_VALUE-5;
        while (L < R){
            long mid = (L+R)/2;
            if (getZero(mid) < k){
                L = mid+1;
            }else {
                R = mid;
            }
        }
        if (getZero(R) == k){
            System.out.println(R);
        }else {
            System.out.println(-1);
        }
        //long end = System.currentTimeMillis();
        //System.out.println(end-start);
    }
    public static void get(){
        System.out.print("{");
        long i=5;
        while (i< 2e18){
            System.out.print(i+"L,");
            i*=5;
        }
        System.out.print("}");
    }

    public static long getZero(long n){
        long ans = 0L;
        for (long l : arr) {
            ans += n / l;
        }
        return ans;
    }
}