计算 1 到 n 的累乘,注意使用 64 位整数避免溢出。
OJ: roj
题目 ID: 5021
难度:入门
标签:模拟循环
创建: 2026-10-08 22:15
更新: 2026-10-08 22:15
形式化题目
给定一个正整数
其中阶乘的定义为:
正解
思路
按题目要求,利用一个循环从
本题的重点是数值类型的上限:
由于 int)的上限约为 int 的范围。
而 long long)的上限约为 long long 类型的变量来存储累乘的结果。
对于 Python,由于内置了任意精度的大整数类型,不存在数值溢出问题,可直接运算。
针对
代码
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 22:08
# update_at: 2026-10-08 22:08
import sys
def solve() -> None:
"""读入 n,输出 1×2×…×n;Python 整数无限精度,不存在 20! 溢出问题。"""
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
ans = 1
for i in range(1, n + 1):
ans *= i
print(ans)
if __name__ == "__main__":
solve()/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 22:08
* update_at: 2026-10-08 22:08
*/
// main.cpp:一本通 2019:【例4.4】求阶乘。
// 题面:读入正整数 n(1 ≤ n ≤ 20),用 for 循环输出 n! = 1×2×…×n。
// 关键点:int 上限 2^31-1 = 2147483647,从 n = 13 起 n! = 6227020800 就溢出;
// 20! = 2432902008176640000 < 2^63-1 = 9223372036854775807,用 ll 恰好够。
#include <iostream>
using namespace std;
typedef long long ll;
ll n; // 题面输入的正整数,1 ≤ n ≤ 20
void read_input() {
cin >> n;
}
// 从 1 累乘到 n。累乘变量初值必须是 1(本题 n ≥ 1)。
void solve() {
ll ans = 1;
for (ll i = 1; i <= n; i++) {
ans *= i;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
- 时间复杂度:
。循环遍历 到 ,执行 次乘法操作。由于 ,运算极快。 - 空间复杂度:
。仅需常数个变量存储输入和累乘结果。
总结
-
核心算法:利用递推
,通过一重循环累乘解决,时间复杂度 。 -
数据类型是本题的核心考点: 最小溢出
int的值为( )。 ,因此 long long刚好够用。 若将代码中的long long替换为int,在的全枚举中会导致 8/20 个点失败。实测对比表如下: int版输出正确答案 1–12 一致 一致 13 1932053504 6227020800 17 -288522240 355687428096000 20 -2102132736 2432902008176640000 可以看出,
long long是本题的强制要求。 -
数据覆盖是有意的:测试数据中的
problem7()恰好是首个导致 int溢出的最小,说明出题人有意考察了溢出边界。测试数据中也存在 的边界和 的上限值。 -
Python 无溢出问题:Python 的整数类型支持任意精度,不用担心溢出。
-
验证强度摘要:本题通过
math.factorial和bc任意精度计算器两路异源进行了的全枚举比对,分歧为 0;通过扰动测试排除了面向用例编程,代码中的字面量亦不包含答案值,解法真实可靠。