【例4.12】阶乘和

GitHub跳转原题关系图返回列表

通过单层循环同时维护当前项的阶乘与前缀阶乘和,将时间复杂度从 O(n²) 优化为 O(n) 的基础递推应用。

OJ: roj

题目 ID: 5028

难度:入门

标签:循环递推

创建: 2026-10-08 22:28

更新: 2026-10-08 22:28

形式化题目

给定一个正整数 nn(1≤n≤101 \le n \le 10),求: S=1!+2!+3!+⋯+n!S = 1! + 2! + 3! + \dots + n!

其中 k!=1×2×⋯×kk! = 1 \times 2 \times \dots \times k。最后输出 SS 的值。

正解

思路

这道题目要求我们求出前 nn 个数的阶乘之和。

最朴素的做法是对于每一个 k∈[1,n]k \in [1, n],都使用一个循环从 11 乘到 kk 算出 k!k!,然后再将它们累加。由于计算每一个 k!k! 需要 kk 次乘法,总的运算次数大约是 1+2+⋯+n=n(n+1)21 + 2 + \dots + n = \frac{n(n+1)}{2},时间复杂度为 O(n2)O(n^2)。

优化点: 我们观察到相邻的两项阶乘之间存在严格的递推关系: k!=(k−1)!×kk! = (k-1)! \times k 这意味着,如果我们已经算出了 (k−1)!(k-1)!,只需要再乘上 kk 就能得到 k!k!,完全不需要每次都从头开始连乘。

因此,我们可以用单层循环同时维护两个变量:

  1. fac 表示当前的阶乘项,初始为 11。在第 ii 次循环时,更新 fac = fac * i。
  2. sum 表示阶乘和,初始为 00。在第 ii 次循环算出当前的 fac 后,将其累加到 sum 中,即 sum = sum + fac。

这样,每次循环只需要常数次的乘法和加法操作,整个算法的时间复杂度就从 O(n2)O(n^2) 降低到了 O(n)O(n)。在教学中,这是一种典型的利用“递推思想”消除冗余计算的例子。

对于数据范围的考量:当 n=10n = 10 时,最大的阶乘项 10!=3,628,80010! = 3,628,800,总和 S10=4,037,913S_{10} = 4,037,913。这一结果远在 32 位有符号整数(int)的上限 2,147,483,6472,147,483,647 以内,本题数据不会造成溢出。不过本仓库约定「题目数据默认 long long」,因此代码中 fac、sum 仍声明为 ll(typedef long long ll)——即使评测数据超出题面范围(如 n≥13n \ge 13)也不会溢出。

代码

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;
}

复杂度

  • 时间复杂度:O(n)O(n)。只需遍历从 11 到 nn 的单层循环,每次循环内执行 O(1)O(1) 的基本运算。
  • 空间复杂度:O(1)O(1)。只使用了几个整型变量来存储中间结果和答案。

总结

  • 递推思想:Sn=Sn−1+n!S_n = S_{n-1} + n!,维护前缀积 fac *= i 同时 sum += fac,算法从 O(n2)O(n^2) 优化为 O(n)O(n),空间 O(1)O(1)。
  • 递推与「每项重算」等价性的论证:两种写法求的是同一个数学量。整数乘法满足结合律,1⋅2⋯(k−1)⋅k1 \cdot 2 \cdots (k-1) \cdot k 与重头乘一遍得到同一个精确整数(无舍入);且两者都以 k=1..nk = 1..n 的同一顺序累加同样的项,整数加法结合律和交换律保证和逐位相同。
  • 类型选择与溢出边界:本题用 int 也确实能过(10!=3,628,80010! = 3{,}628{,}800、S10=4,037,913S_{10} = 4{,}037{,}913 均远小于 231−12^{31}-1),代码中改成 ll 是遵循仓库规范而非修 bug。反事实数据实测表明:在 n=1..10n=1..10 内 int 版与 ll 版输出逐字节完全相同;12!=479,001,60012! = 479{,}001{,}600 尚在 int 内,但 n=13n = 13 时 13!=6,227,020,80013! = 6{,}227{,}020{,}800 就已超过 231−12^{31}-1。所以本题代码直接使用 long long(可安全算到 n=20n = 20,S20=2,561,327,494,111,820,313S_{20} = 2{,}561{,}327{,}494{,}111{,}820{,}313;n≥21n \ge 21 才超过 263−12^{63}-1)。首次超 int 是 n=13n=13,首次超 ll 是 n=21n=21。当 n=13n=13 时,ll 版输出正确的 6749977113,而 int 版因溢出输出 -1839957479,此时才分道扬镳。
  • 验证强度摘要:
    • 本题经过了四者逐字节比对(C++ 版 / Python 版 / math.factorial 独立暴力求解 / 数据 data 的 10 个 .out)且 0 分歧。
    • V5 扰动验证:将 fac *= i 改为 fac *= 1 会导致 n=10n=10 输出从 4037913 变成 10,确系枚举算出。
    • V2 非硬编码:源码的数值字面量集合不包含答案值(如 4037913、3628800 等),保证无硬编码。
  • 边界:当 n=1n=1 时正常进入循环并输出 11;题目测试数据严格保证 n∈{1..10}n \in \{1..10\} 且每个值恰好对应一个点。