E题求阶乘

只是记录一下个人的思路，若有错误还请指正

试题 E: 求阶乘
时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】
满足 N! 的末尾恰好有 K 个 0 的最小的 N 是多少?如果这样的 N 不存在输出 −1。
【输入格式】
一个整数 K。

【输出格式】
一个整数代表答案。

【样例输入】
2

【样例输出】
10

【评测用例规模与约定】
对于 30% 的数据，1 ≤ K ≤ 106.
对于 100% 的数据，1 ≤ K ≤ 1018.
 

求n的阶乘的尾数零的数量，这个跟从 1 ~ n 中的因子 5 的数量成正比

    public int get5(int n){
        
        int res = 0;
        for(int i = 5; i <= n; i += 5){
            int j = i;
            while(j > 0){
                res ++;
                j /= 5;
            }
        }
        return res;
    }

如果按照这种方法求的话，肯定在k较大时会超时

还有另一种求n的阶乘中尾数零的方法（不会证明，我是记住的）

                while (n > 0) {
                    res += n / 5;
                    n /= 5;

                }

这样可以直接求得n的阶乘中尾数零的数量，大概是O(logN)，如果再加上 二分查找 n 的位置，一定可以求得这个 n

附上代码（不知道对错啊）

import java.util.Scanner;
public class E {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        long k = in.nextLong();

        long res = 0;
        long l = 5, r = 5000000000000000000L;
        long n = 0;
        long mid = 0;
        //如果是 k = 5， n = 20时有4个尾数零，n = 25时有6个尾数零，那么找不到一个res == k，就会 l >= r
        while (l < r) {
            res = 0;
            n = l + r >> 1;
            mid = n;
            while (n > 0) {
                res += n / 5;
                n /= 5;

            }
            if (res < k) {
                l = mid + 1;
            } else if (res > k) {
                r = mid;
            } else {
                //答案应该都刚好是5的倍数吧，如果不再处理一下，二分找到的可能很多都不是5的倍数
                while ((mid % 5) != 0) {
                    mid--;
                }
                System.out.println(mid);
                return;
            }

        }
        System.out.println(-1);
    }
}