第十三届蓝桥杯JavaB组省赛E题——求阶乘 （AC）

1.求阶乘

1.问题描述

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

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

2.输入格式

一个整数 $K$ 。

3.输出格式

一个整数代表答案。

4.样例输入

2

5.样例输出

10

6.数据范围

$1\le K\le 10^{18}$

7.原题链接

求阶乘

2.解题思路

注意到 $k$ 的值最大达到1e18，这意味着我们最多只能使用 $O(logn)$ 的复杂度，这个复杂度的算法我们应该直观地想到二分。

既然想使用二分，那就需要考虑是否满足二段性，设 $n$ 为答案，当 $mid$ 小于 $n$ 时，$mid$阶乘末尾 0 的个数一定小于 $k$ ，当 $mid$ 大于等于 $n$ 时，$,mid$ 阶乘末尾 0 的个数一定 不小于 $k$ 。由此可知这是符合二段性的，说明我们可以二分 。

当然判断某个数的阶乘的末尾 0 个数，我们也不能暴力的去计算，一个比较常用的技巧则是判断一个数可拆分出 $2$ 的个数和 $5$ 的个数，由于是阶乘，可知 $2$ 出现的次数一定比 $5$ 多，所以我们只需要看 $n!$ 能拆分出多少个 $5$ ，则可知它的阶乘有多少个 0。

在计算 $n！$ 可以拆分多少个 $5$ 的个数时，先筛选出能拆分出 1 个 5 的数有哪些，再筛出能拆分 2 个 5 的倍数有哪些，以此类推。如2x5=10，说明10可以拆出1个5，如5x5=25，说明25可以拆出2个5。这样我们只需要不断的将 n 除以 5 并累计结果，即可在 $log$ 的复杂度计算出结果。

最后二分得到的答案还需要判断阶乘末尾0的个数是否恰好为 $k$ 个，因为我们只能保证不少于 $k$ 个，并不一定恰好是 $k$ 个。

同时需要注意二分的上界 r ，需要保证足够大才能得到答案，可以自己猜一下然后看能否跑出 $k$= 1e18 时的答案，这里开的 9e18 。
时间复杂度：可视为$O(log(9e18)\ast logn)$

3.AC_code

C++

#include
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL query(LL x)
{
    LL ans = 0;
    while (x > 0) {
        ans += x / 5;
        x /= 5;
    }
    return ans;
}
LL k;
void solve()
{
    cin >> k;
    LL l = 1, r =9e18;
    while (l < r)
    {
        LL mid = l + (r - l) / 2;
        if (query(mid) >= k) r = mid;
        else l = mid + 1;
    }
    LL x = query(r);
    cout << (x == k ? r : -1) << '\n';
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long k = sc.nextLong();
        long l = 1, r = (long) 9e18;
        while (l < r) {
            long mid = l + (r - l) / 2;
            if (query(mid) >= k) r = mid;
            else l = mid + 1;
        }
        long x = query(r);
        System.out.println(x == k ? r : -1);
    }

    static long query(long x) {
        long ans = 0;
        while (x > 0) {
            ans += x / 5;
            x /= 5;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

.