1.求阶乘

1.问题描述

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

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

2.输入格式

一个整数 K K K 。

3.输出格式

一个整数代表答案。

4.样例输入

2

5.样例输出

10

6.数据范围

1 ≤ K ≤ 1 0 18 1leq K leq 10^{18} 1≤K≤1018

7.原题链接

2.解题思路

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

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

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

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

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

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

3.AC_code

C++

#include<bits/stdc++.h>
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 = 1e20;
    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) << 
;
}
int main()
{
          
   
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
    {
          
   
        solve();
    }
    return 0;
}

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) 1e20;
        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;
    }
}

.