P1009 阶乘之和

calendar May 5, 2026 · 4 分钟阅读 · 高精度  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1009
难度 橙题（普及-）
知识点 高精度、循环

题目描述

用高精度计算出：

S = 1! + 2! + 3! + ... + n! (n ≤ 50)

其中 ! 表示阶乘，定义为 n! = n × (n-1) × ... × 1，特别地 0! = 1。

输入格式：一个整数 n。

输出格式：一个整数，表示阶乘之和 S。

解题思路

核心思想

由于 n ≤ 50，50! 已经是一个非常大的数（约 65 位十进制数字），超出了任何内置整数类型的范围，因此必须使用高精度来计算。

整体思路分两步：

  1. 递推计算阶乘：利用 (i-1)! 计算 i!，避免重复计算
  2. 高精度加法：将每个阶乘的结果累加到总和中

高精度实现思路

我们用低位优先的方式存储大整数：用一个数组（或 vector）从下标 0 开始存放个位、十位、百位……

例如数字 12345 存储为 [5, 4, 3, 2, 1]。

需要两个基本操作：

  • 高精度 × 低精度：计算 a *= b（b 是普通整数）
  • 高精度 + 高精度：计算 a += b

完整代码

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 高精度乘法：digits（低位优先）乘以一个普通整数 multiplier
void multiply(vector<int>& digits, int multiplier) {
    int carry = 0;
    for (int i = 0; i < digits.size(); i++) {
        carry += digits[i] * multiplier;
        digits[i] = carry % 10;
        carry /= 10;
    }
    while (carry) {
        digits.push_back(carry % 10);
        carry /= 10;
    }
}

// 高精度加法：a += b（a、b 均为低位优先）
void add(vector<int>& a, const vector<int>& b) {
    int carry = 0;
    int max_len = max(a.size(), b.size());
    a.resize(max_len, 0);
    for (int i = 0; i < max_len; i++) {
        int digit_b = i < b.size() ? b[i] : 0;
        carry += a[i] + digit_b;
        a[i] = carry % 10;
        carry /= 10;
    }
    if (carry) {
        a.push_back(carry);
    }
}

// 打印高精度数（低位优先存储，打印时需逆序）
void print_big(const vector<int>& digits) {
    for (int i = digits.size() - 1; i >= 0; i--) {
        cout << digits[i];
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> factorial = {1};  // 0! = 1
    vector<int> sum = {0};         // 总和，初始为 0

    for (int i = 1; i <= n; i++) {
        multiply(factorial, i);   // factorial 现在等于 i!
        add(sum, factorial);       // sum += i!
    }

    print_big(sum);
    return 0;
}

Python

"""P1009 阶乘之和 - Python 实现（高精度）"""
from typing import List


def solve() -> None:
    """读取 n，计算 1! + 2! + ... + n! 并输出"""
    n: int = int(input().strip())

    factorial: int = 1   # 当前阶乘值
    total: int = 0        # 阶乘之和

    for i in range(1, n + 1):
        factorial *= i      # i! = (i-1)! × i
        total += factorial

    print(total)


if __name__ == "__main__":
    solve()

Java

import java.io.IOException;
import java.math.BigInteger;

public class Main {
    // 洛谷强制要求类名为 Main，禁止使用 Scanner，用 BufferedInputStream
    private static final byte[] BUFFER = new byte[1 << 16];
    private static int ptr = 0;
    private static int len = 0;

    private static int read() throws IOException {
        if (ptr >= len) {
            len = System.in.read(BUFFER);
            ptr = 0;
            if (len <= 0) return -1;
        }
        return BUFFER[ptr++];
    }

    private static int readInt() throws IOException {
        int c, val = 0;
        do {
            c = read();
        } while (c <= ' ' && c != -1);
        boolean neg = (c == '-');
        if (neg) c = read();
        while (c > ' ') {
            val = val * 10 + (c - '0');
            c = read();
        }
        return neg ? -val : val;
    }

    public static void main(String[] args) throws IOException {
        int n = readInt();

        BigInteger factorial = BigInteger.ONE;  // 0! = 1
        BigInteger sum = BigInteger.ZERO;

        for (int i = 1; i <= n; i++) {
            factorial = factorial.multiply(BigInteger.valueOf(i));  // i!
            sum = sum.add(factorial);                             // sum += i!
        }

        System.out.println(sum);
    }
}

Go

package main

import (
    "bufio"
    "fmt"
    "math/big"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)

    var n int
    fmt.Fscan(in, &n)

    factorial := big.NewInt(1)  // 0! = 1
    sum := big.NewInt(0)       // 总和

    for i := 1; i <= n; i++ {
        factorial.Mul(factorial, big.NewInt(int64(i)))  // i!
        sum.Add(sum, factorial)                          // sum += i!
    }

    fmt.Println(sum)
}

JavaScript

'use strict';

/**
 * 计算 1! + 2! + ... + n!（使用 BigInt 高精度）
 */
function main() {
    const input = require('fs').readFileSync(0, 'utf8').trim().split(/\s+/);
    const n = Number(input[0]);

    let factorial = 1n;  // 当前阶乘值（BigInt）
    let sum = 0n;        // 阶乘之和（BigInt）

    for (let i = 1; i <= n; i++) {
        factorial *= BigInt(i);   // i!
        sum += factorial;          // sum += i!
    }

    console.log(sum.toString());
}

main();

关键代码讲解

1. 低位优先存储

// 数字 12345 存储为 [5, 4, 3, 2, 1]
vector<int> digits = {5, 4, 3, 2, 1};

这样设计的好处是：进位和扩展位数只需要 push_back，不需要移动整个数组。

2. 高精度乘法（大数 × 小数）

void multiply(vector<int>& digits, int multiplier) {
    int carry = 0;
    for (int i = 0; i < digits.size(); i++) {
        carry += digits[i] * multiplier;
        digits[i] = carry % 10;   // 当前位
        carry /= 10;               // 进位
    }
    while (carry) {               // 还有进位，扩展位数
        digits.push_back(carry % 10);
        carry /= 10;
    }
}

3. Python 的天然优势

Python 内置支持任意精度整数，直接写 factorial *= i 即可，不需要手动实现高精度，代码非常简洁。

复杂度分析

方法 时间复杂度 空间复杂度
高精度模拟 O(n × L) O(L)

其中 L 是结果的位数，L ≈ log10(n!) ≈ n log10 n。

易错点

  1. 进位处理不彻底：乘法中 while (carry) 不能省略，否则高位会丢失
  2. 加法位数不对齐：两个加数的位数可能不同，需要先 resize 再计算
  3. 打印顺序：存储是低位优先，打印时必须逆序输出
  4. n 的范围：n=50 时结果约有 65 位，任何内置类型都存不下，必须用高精度