通过单层循环同时维护当前项的阶乘与前缀阶乘和,将时间复杂度从 O(n²) 优化为 O(n) 的基础递推应用。
OJ: roj
题目 ID: 5028
难度:入门
标签:循环递推
创建: 2026-10-08 22:28
更新: 2026-10-08 22:28
形式化题目
给定一个正整数
其中
正解
思路
这道题目要求我们求出前
最朴素的做法是对于每一个
优化点:
我们观察到相邻的两项阶乘之间存在严格的递推关系:
因此,我们可以用单层循环同时维护两个变量:
fac表示当前的阶乘项,初始为。在第 次循环时,更新 fac = fac * i。sum表示阶乘和,初始为。在第 次循环算出当前的 fac后,将其累加到sum中,即sum = sum + fac。
这样,每次循环只需要常数次的乘法和加法操作,整个算法的时间复杂度就从
对于数据范围的考量:当 int)的上限 long long」,因此代码中 fac、sum 仍声明为 ll(typedef long long ll)——即使评测数据超出题面范围(如
代码
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:19
# update_at: 2026-10-08 22:22
import sys
def solve() -> None:
"""读入 n,单层循环递推累加 1! + 2! + ... + n!;Python 整数无溢出问题。"""
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
fac = 1 # fac:当前项 i!(初始 1 表示 0!)
total = 0 # total:1! + 2! + ... + i!
for i in range(1, n + 1):
fac *= i # 利用 i! = (i-1)! * i,避免每次从头连乘
total += fac
print(total)
if __name__ == "__main__":
solve()cpp
/**
* 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:19
* update_at: 2026-10-08 22:22
*/
// 一本通 2026《【例4.12】阶乘和》:输入正整数 n,求 S = 1! + 2! + ... + n!。
// 数据范围(题面【提示】):1 <= n <= 10。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n; // 输入的正整数 n,题面保证 1 <= n <= 10
// 递推求阶乘和:fac 始终保存当前项 i!,sum 累加 1!..i!,单重循环 O(n)。
// n = 10 时 10! = 3628800、S = 4037913,int 也装得下;
// 但按本仓库规范「题目数据默认 ll」,仍统一用 long long,越界输入也不会溢出。
void solve() {
ll fac = 1; // fac:进入第 i 轮后乘上 i 即为 i!
ll sum = 0; // sum:1! + 2! + ... + i!
for (ll i = 1; i <= n; i++) {
fac *= i;
sum += fac;
}
cout << sum << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n)) {
return 0; // 空输入时直接退出
}
solve();
return 0;
}复杂度
- 时间复杂度:
。只需遍历从 到 的单层循环,每次循环内执行 的基本运算。 - 空间复杂度:
。只使用了几个整型变量来存储中间结果和答案。
总结
- 递推思想:
,维护前缀积 fac *= i同时sum += fac,算法从优化为 ,空间 。 - 递推与「每项重算」等价性的论证:两种写法求的是同一个数学量。整数乘法满足结合律,
与重头乘一遍得到同一个精确整数(无舍入);且两者都以 的同一顺序累加同样的项,整数加法结合律和交换律保证和逐位相同。 - 类型选择与溢出边界:本题用
int也确实能过(、 均远小于 ),代码中改成 ll是遵循仓库规范而非修 bug。反事实数据实测表明:在内 int版与ll版输出逐字节完全相同;尚在 int内,但时 就已超过 。所以本题代码直接使用 long long(可安全算到, ; 才超过 )。首次超 int是,首次超 ll是。当 时, ll版输出正确的6749977113,而int版因溢出输出-1839957479,此时才分道扬镳。 - 验证强度摘要:
- 本题经过了四者逐字节比对(C++ 版 / Python 版 /
math.factorial独立暴力求解 / 数据data的 10 个.out)且 0 分歧。 - V5 扰动验证:将
fac *= i改为fac *= 1会导致输出从 4037913变成10,确系枚举算出。 - V2 非硬编码:源码的数值字面量集合不包含答案值(如
4037913、3628800等),保证无硬编码。
- 本题经过了四者逐字节比对(C++ 版 / Python 版 /
- 边界:当
时正常进入循环并输出 ;题目测试数据严格保证 且每个值恰好对应一个点。