【例4.4】求阶乘

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

计算 1 到 n 的累乘,注意使用 64 位整数避免溢出。

OJ: roj

题目 ID: 5021

难度:入门

标签:模拟循环

创建: 2026-10-08 22:15

更新: 2026-10-08 22:15

形式化题目

给定一个正整数 nn(1≤n≤201 \le n \le 20),求 nn 的阶乘 n!n!。

其中阶乘的定义为:n!=1×2×⋯×nn! = 1 \times 2 \times \dots \times n。

正解

思路

按题目要求,利用一个循环从 11 遍历到 nn,并将每个数累乘到结果变量中。

本题的重点是数值类型的上限: 由于 nn 最大为 2020,而 20!=243290200817664000020! = 2432902008176640000。 3232 位有符号整数(int)的上限约为 2×1092 \times 10^9,无法存放 20!20! 的结果,会发生溢出。具体来说,当 n=13n = 13 时,13!=6227020800>231−113! = 6227020800 > 2^{31}-1,会首次超出 int 的范围。 而 6464 位有符号整数(long long)的上限约为 9.22×10189.22 \times 10^{18},可以安全存储 20!20!,因此本题在 C/C++ 中需要使用 long long 类型的变量来存储累乘的结果。 对于 Python,由于内置了任意精度的大整数类型,不存在数值溢出问题,可直接运算。

针对 n=1n=1 的边界情况,循环从 11 开始,执行 11 次后结果刚好为 11。

代码

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()
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: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;
}

复杂度

  • 时间复杂度:O(n)O(n)。循环遍历 11 到 nn,执行 nn 次乘法操作。由于 n≤20n \le 20,运算极快。
  • 空间复杂度:O(1)O(1)。仅需常数个变量存储输入和累乘结果。

总结

  • 核心算法:利用递推 n!=1×2×⋯×nn! = 1 \times 2 \times \cdots \times n,通过一重循环累乘解决,时间复杂度 O(n)O(n)。

  • 数据类型是本题的核心考点: 最小溢出 int 的值为 n=13n = 13(12!≤231−1<13!12! \le 2^{31}-1 < 13!)。20!=2432902008176640000<263−120! = 2432902008176640000 < 2^{63}-1,因此 long long 刚好够用。 若将代码中的 long long 替换为 int,在 n=1..20n=1..20 的全枚举中会导致 8/20 个点失败。实测对比表如下:

    nn int 版输出 正确答案
    1–12 一致 一致
    13 1932053504 6227020800
    17 -288522240 355687428096000
    20 -2102132736 2432902008176640000

    可以看出,long long 是本题的强制要求。

  • 数据覆盖是有意的:测试数据中的 problem7(n=13n=13)恰好是首个导致 int 溢出的最小 nn,说明出题人有意考察了溢出边界。测试数据中也存在 n=1→1n=1 \to 1 的边界和 n=20n=20 的上限值。

  • Python 无溢出问题:Python 的整数类型支持任意精度,不用担心溢出。

  • 验证强度摘要:本题通过 math.factorial 和 bc 任意精度计算器两路异源进行了 n=1..20n=1..20 的全枚举比对,分歧为 0;通过扰动测试排除了面向用例编程,代码中的字面量亦不包含答案值,解法真实可靠。