求阶乘-二分查找-求阶乘中某质因子个数(java)

解题思路:

    只需要知道2和5可以组成一个零，并且2的数量总会比5多，所有只需要求解阶乘中质因数5的个数就可以求出阶乘中后导零的个数

    所以问题变成了：求阶乘中某质因子个数：
        只需将n循环整除所要求的质因子并将得数相加就行

private static long f(long n){
    long ans = 0;
    while (n >= 5){
        ans += n/5;
        n /= 5;
    }
    return ans;
}

接着就是在1 ≤ K ≤ 10的18次方的范围内进行二分查找

参考代码:

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long k = sc.nextLong();
        long start = 5;
        long end = 4000000000000000020L;
        while (start  k){
                end = mid - 1;
            }else if(temp < k){
                start = mid + 1;
            }else {
                while (mid % 5 != 0){
                    mid --;
                }
                System.out.println(mid);
                return;
            }
        }
        System.out.println(-1);
    }

    private static long f(long n){
        long ans = 0;
        while (n >= 5){
            ans += n/5;
            n /= 5;
        }
        return ans;
    }
}