当前位置：首页 > 入门组 > 1998年NOIP普及组阶乘之和题解（洛谷P1009） | 高精度算法实现与解题思路分析

1998年NOIP普及组阶乘之和题解（洛谷P1009） | 高精度算法实现与解题思路分析

6个月前 (08-26)

一、题目解读

1998年NOIP普及组阶乘之和（洛谷P1009）要求计算前n个自然数的阶乘之和，即 ∑(i=1 to n) i!。由于阶乘结果随n增长迅速膨胀（例如，n=20时，20!已远超常规整数类型上限），题目核心难点在于如何高精度处理大数相加与乘法运算。传统数据类型无法直接存储计算结果，需设计自定义高精度算法解决。

二、解题思路

用户提供的代码采用高精度分治策略：

1. 核心思想：通过动态数组存储大数，逐位模拟乘法和加法过程，解决数值溢出问题。

2. 关键步骤：

定义高精度乘法函数 multiply(a, b)，实现大数a与整数b的乘积（逐位相乘+进位处理）。

定义高精度加法函数 add(a, b)，实现两个大数a与b的逐位相加（考虑位数差异与进位）。

主循环：从1到n依次计算i的阶乘，并累加至总和。

3. 优化点：逆序输出结果避免字符串反转，提升效率。

三、解题步骤

1. 初始化：

总和 sum 初始化为向量[0]，阶乘 fact 初始化为[1]。

2. 循环计算：

外层循环i从1到n，逐次处理每个阶乘项。

内层：

a. 计算 fact = multiply(fact, i)，更新当前阶乘。

b. 累加 sum = add(sum, fact)，将阶乘加入总和。

3. 输出处理：逆序遍历sum向量，输出各位数字（因存储为逆序，直接输出即正确结果）。

四、代码与注释

#include <iostream>
#include <vector>
using namespace std;

// 高精度乘法：大数a乘以整数b
vector<int> multiply(vector<int> a, int b) {
    vector<int> c;
    int carry = 0; // 进位
    for (int i = 0; i < a.size(); i++) {
        int temp = a[i] * b + carry; // 当前位乘积+进位
        c.push_back(temp % 10); // 取个位存入结果
        carry = temp / 10; // 更新进位
    }
    while (carry) { // 处理末尾进位
        c.push_back(carry % 10);
        carry /= 10;
    }
    return c;
}

// 高精度加法：大数a加上大数b
vector<int> add(vector<int> a, vector<int> b) {
    vector<int> c;
    int carry = 0;
    for (int i = 0; i < max(a.size(), b.size()); i++) { // 按较长位数对齐
        int sum = carry; // 初始化本位和
        if (i < a.size()) sum += a[i];
        if (i < b.size()) sum += b[i];
        c.push_back(sum % 10);
        carry = sum / 10;
    }
    if (carry) c.push_back(carry); // 处理最高位进位
    return c;
}

int main() {
    int n;
    cin >> n; // 输入n
    
    vector<int> sum(1, 0); // 总和初始化为[0]
    vector<int> fact(1, 1); // 阶乘初始化为[1]
    
    for (int i = 1; i <= n; i++) {
        fact = multiply(fact, i); // 计算i的阶乘
        sum = add(sum, fact); // 累加至总和
    }
    
    // 逆序输出结果
    for (int i = sum.size() - 1; i >= 0; i--) {
        cout << sum[i];
    }
    cout << endl;
    
    return 0;
}