【数学, 二分查找】求阶乘【蓝桥杯】

题目

4666. 求阶乘 - AcWing题库

求阶乘 - 蓝桥云课

---

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

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

输入格式

一个整数 $K$ 。

输出格式

一个整数代表答案。

数据范围

对于 $30\%$ 的数据， $1 ≤ K ≤ 10^6$ 。
对于 $100\%$ 的数据， $1 ≤ K ≤ 10^{18}$ 。

输入样例：

2

输出样例：

10

解题

方法一：数学 分解质因数 二分查找

思路

$N!$ 末尾 $0$ 的数量取决于其因子 $2$ 的数量与其因子 $5$ 的数量，而因子 $2$ 的数量显然比因子 $5$ 要多，所以末尾 $0$ 的数量实际上等于 $N!$ 分解质因数后 $5$ 的数量。

求 $n$ 的阶乘中因子 $x$ 的数量：$cnt(x) = \sum_{i=1}^{\lfloor\log_{x}{n}\rfloor}{\lfloor\frac{n}{x^i}\rfloor}$ （也就是 $cnt(x) = \lfloor \frac{n}{x} \rfloor + \lfloor \frac{n}{x^2} \rfloor + ... + \lfloor \frac{n}{x^i} \rfloor, \enspace x^i \le n$ ）。

有了以上的公式，只需要二分查找满足 $cnt(5) = K$ 的情况下 $N$ 的最小值即可。

（实际做题中二分查找的条件是 $cnt(5) \ge K$，最后判断如果 $cnt(5) = K$ 则输出 $N$，否则不存在这样的 $N$ 输出 $−1$ ）

代码

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    static long count(long n) {
        long cnt = 0;
        while (n > 0) cnt += n /= 5;
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        long k = Long.parseLong(in.readLine());
        long l = 0L, r = Long.MAX_VALUE;
        while (l < r) {
            long m = l + (r - l >> 1);
            if (count(m) >= k) r = m;
            else l = m + 1;
        }
        System.out.println(count(l) == k ? l : -1);
    }
}