当前位置：首页 > article >正文

lanqiaoOJ 2145：求阶乘 ← 二分法

article 2025/1/31 1:24:02

【题目来源】
https://www.lanqiao.cn/problems/2145/learning/

【题目描述】
满足 N！的末尾恰好有 K 个 0 的最小的 N 是多少？
如果这样的 N 不存在输出 -1。

【输入格式】
一个整数 K。

【输出格式】
一个整数代表答案。

【输入样例】
2

【输出样例】
10

【评测用例规模与约定】
对于 30% 的数据，1≤K≤10^6.
对于 100% 的数据，1≤K≤10^18.

【算法分析】
● 二分法的应用条件是“序列是单调有序的”，这题满足吗？因为 n 递增时，尾零的数量也是单调递增的，符合二分应用条件。

● 给定 n!，其 2*5 出现的次数，即是 n! 的末尾出现 0 的次数。而 n! 中，因子 2 出现的次数多，因子 5 出现的次数少，所以统计 2*5 出现的次数就转化为统计 5 出现的次数。

● 当数据比较大时，可能会产生溢出。所以，本题中使用 mid=le+(ri-le)/2 而不是 mid=(le+ri)/2。

【算法代码】

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

LL check(LL x) {
    LL ans=0;
    while(x>0) {
        ans+=x/5;
        x/=5;
    }
    return ans;
}

int main() {
    LL k;
    cin>>k;
    LL le=1, ri=1e19;
    while(le<ri) {
        LL mid=le+(ri-le)/2;
        if(check(mid)>=k) ri=mid;
        else le=mid+1;
    }
    LL x=check(ri);
    cout<<(x==k?ri:-1)<<endl;

    return 0;
}

/*
in:
2

out:
10
*/

【参考文献】
https://mp.weixin.qq.com/s/wV_bAQGg1TItv0Tk-FJiOg
https://blog.csdn.net/hnjzsyjyj/article/details/136764077
https://blog.csdn.net/hnjzsyjyj/article/details/136827860

查看全文

http://www.kler.cn/a/525332.html