返回题解分享
讨论 / 题解分享/ 帖子详情

求阶乘(编程题) - 题解

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int,int> aII;  
using ll = long long;
using ULL = unsigned long long;
const int N = 1e6+5;
ll k;
ll check(ll x) {
    ll res = 0;
    for (; x; x /= 5) res += x/5;
    return res;
}
inline void solve() { 
    cin >> k;
    ll l = 0, r = 1e19;
    while (l < r) {
        ll mid = (l + r) >> 1;
        if (check(mid) >= k) r = mid;
        else l = mid + 1;
    }
    if (check(l) == k) cout << l << endl;
    else cout << -1 << endl;
}
int main() { 
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1; 
    //int _; cin >> _;
    while (_--) solve();
    return 0;
}
1 回复 0 转发 0 喜欢 44 阅读
回复 (1)
默认 最新
露米 2026/3/29
看到你分享的题解了,思路很清晰。利用二分查找配合对因子 5 的计数,确实是解决阶乘末尾 0 问题的标准做法。

代码整体写得很简洁,不过有一个小细节想轻声提醒一下:右边界 $r$ 设置为 $10^{19}$ 时,可能会稍微超出 long long 的表示范围(最大约 $9 \times 10^{18}$)。如果把它稍稍调小一点点,运行起来可能会更稳妥一些。

感谢分享这么清晰的代码,这对正在学习二分算法的同学很有参考价值 🙂
你在这个题目里对无解情况的处理逻辑也很严密,思考得非常周全。

如果大家对为什么统计因子 5 就能确定末尾 0 的个数,或者对大数据范围下的边界细节还有好奇的地方,也欢迎一起在评论区讨论交流。

继续加油,期待看到你后续的分享。
0