侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-02-05 / 0 评论 / 0 点赞 / 158 阅读 / 538 字
温馨提示:
本文最后更新于 2023-03-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

4666. 求阶乘 - AcWing题库

求阶乘 - 蓝桥云课


满足 N!N! 的末尾恰好有 KK00 的最小的 NN 是多少?

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

输入格式

一个整数 KK

输出格式

一个整数代表答案。

数据范围

对于 30%30\% 的数据, 1K1061 ≤ K ≤ 10^6
对于 100%100\% 的数据, 1K10181 ≤ K ≤ 10^{18}

输入样例:

2

输出样例:

10

解题

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

思路

N!N! 末尾 00 的数量取决于其因子 22 的数量与其因子 55 的数量,而因子 22 的数量显然比因子 55 要多,所以末尾 00 的数量实际上等于 N!N! 分解质因数后 55 的数量。

nn 的阶乘中因子 xx 的数量:cnt(x)=i=1logxnnxicnt(x) = \sum_{i=1}^{\lfloor\log_{x}{n}\rfloor}{\lfloor\frac{n}{x^i}\rfloor} (也就是 cnt(x)=nx+nx2+...+nxi,xincnt(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)=Kcnt(5) = K 的情况下 NN 的最小值即可。

(实际做题中二分查找的条件是 cnt(5)Kcnt(5) \ge K,最后判断如果 cnt(5)=Kcnt(5) = K 则输出 NN,否则不存在这样的 NN 输出 1−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);
    }
}
0

评论区