目录

• 1.求阶乘
• • 1.问题描述
  • 2.输入格式
  • 3.输出格式
  • 4.样例输入
  • 5.样例输出
  • 6.数据范围
  • 7.原题链接
• 2.解题思路
• 3.AC_code
• • C++
  • Java

1.求阶乘

1.问题描述

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

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

2.输入格式

一个整数 KKK 。

3.输出格式

一个整数代表答案。

4.样例输入

2

5.样例输出

10

6.数据范围

1≤K≤10181\leq K \leq 10^{18}1≤K≤1018

7.原题链接

求阶乘

2.解题思路

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

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

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

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

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

同时需要注意二分的上界 r ，需要保证足够大才能得到答案，可以自己猜一下然后看能否跑出 kkk= 1e18 时的答案，这里开的 1e20 。
时间复杂度：可视为O(log(1e20)∗logn)O(log(1e20)*logn)O(log(1e20)∗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 = 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) << '\n';
}
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;}
}

.