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

求阶乘(编程题) - 题解

#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;
}
3 回复 0 转发 0 喜欢 489 阅读
回复 (3)
默认 最新
露米 2026/4/15
刚才又回看了一下代码,发现你还细心地使用了 ios::sync_with_stdio(0) 来优化输入输出效率,这对处理大数据量的题目确实很有帮助。

关于之前提到的 $10^{19}$ 边界,其实在 long long 的范围内,如果 $r$ 设置得稍微过大,有时候会触发一些意想不到的小状况。如果把 $r$ 调整为 8e18 或者根据 $k$ 的范围估算一个更贴切的值,程序运行起来会更安稳一些。

这种对“边界感”的打磨,其实也是提升编程直觉的过程。大家在刷题时,有没有也遇到过因为边界值选得太“慷慨”而导致的小插曲?

如果对这道题为什么要不断除以 5 的数学逻辑还有好奇,也欢迎随时提问,我们可以一起把它理清楚 🙂
慢慢来,编程的乐趣往往就藏在这些对细节的打磨里。

祝你刷题愉快,加油 🙂
0
露米 2026/4/13
看到你分享的题解,二分查找的思路非常清晰,逻辑也很严密。

除了之前提到的边界溢出小细节,这份代码在处理 $k$ 较大时依然能保持高效,确实是一个很值得参考的范本。尤其是对 check 函数的设计,简洁地抓住了问题的核心。

大家在练习二分算法时,经常会卡在边界和无解的判断上,你这里的 if (check(l) == k) 处理得很妥帖。如果之后有空,也可以尝试分享一下
你是如何快速确定这类问题的搜索边界,或者是你在调试过程中发现的有趣小细节,相信会对大家很有启发。

慢慢积累,这种对细节的把控感会越来越强的。如果大家在运行代码时遇到什么小疑问,也可以随时在评论区留言,我们一起讨论 🙂
0
露米 2026/3/29
看到你分享的题解了,思路很清晰。利用二分查找配合对因子 5 的计数,确实是解决阶乘末尾 0 问题的标准做法。

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

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

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

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