【NOIP】1998真题解析 luogu-P1009 阶乘之和 | GESP四、五级以上可练习

NOIP 1998 普及组真题，主要考察高精度加法与高精度乘法，属于GESP五级考点。适合GESP四、五级以上可练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。

luogu-P1009 [NOIP 1998 普及组] 阶乘之和

题目要求

题目描述

用高精度计算出 $S = 1! + 2! + 3! + \cdots + n!$（$n \le 50$）。

其中 ! 表示阶乘，定义为 $n!=n\times (n-1)\times (n-2)\times \cdots \times 1$。例如，$5! = 5 \times 4 \times 3 \times 2 \times 1=120$。

输入格式

一个正整数 $n$。

输出格式

一个正整数 $S$，表示计算结果。

输入输出样例 #1

输入 #1

3

输出 #1

9

说明/提示

【数据范围】

对于 $100 \%$ 的数据，$1 \le n \le 50$。

---

题目分析

这道题目主要考察了大整数运算，也就是常说的“高精度算法”。题目要求计算 $1! + 2! + \dots + n!$，其中 $n \le 50$。 由于 $50!$ 是一个非常大的数字（约有 65 位），远超出了 C++ 中 long long 的表示范围（最大约是 19 位数）。因此，我们需要自己实现大数据的乘法和加法。

1. 高精度乘法

阶乘的计算可以通过递推完成：$i! = (i-1)! \times i$。 因此，我们需要实现一个“高精度数”乘以“单精度数”（或高精度数）的功能。由于 $i \le 50$，可以用字符串存储长整数来进行模拟手算乘法的过程：

• 从个位开始，用乘数的每一位去乘被乘数的每一位。
• 逐位累加结果，并处理进位。
• 在示例代码中，我们定义了 big_multi 函数，使用 std::vector<int> 来存储按位相乘的中间结果，最后统一处理进位并转回字符串，这样能有效避免中间过程进位错乱。

2. 高精度加法

计算出当前的 $i!$ 后，我们需要将其累加到总和 $S$ 中，即 $S = S + i!$。这需要使用高精度加法。

• 由于加法需要对齐个位，我们可以先将表示数字的字符串进行反转。
• 从低向高依次相加，计算当前位的和加上一轮的进位。
• 最后将结果统一反转回来即可得到和。
• 在代码中，big_sum 实现了这两个字符串表示的大整数相加。

3. 总体流程

• 初始化：当前项的阶乘 multiplier 初始化为 "1"，累加和 ans 初始化为 "1"。
• 循环递推：从 $i = 2$ 开始循环到 $n$，每一步更新 multiplier = big_multi(multiplier, to_string(i))，并将新的阶乘项累加进总和 ans = big_sum(ans, multiplier)。
• 输出结果字符串 ans 即可。

---

示例代码

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

// 高精度乘法：计算两个大整数的乘积
std::string big_multi(std::string a, std::string b) {
    int a_l = a.size();
    int b_l = b.size();
    // 储存按位相乘的结果，最大长度不会超过两个数字长度之和
    std::vector<int> res(a_l + b_l, 0);
    // 模拟竖式乘法，不考虑进位直接相乘累加
    for (int i = a_l - 1; i >= 0; i--) {
        for (int j = b_l - 1; j >= 0; j--) {
            res[i + j] += (a[i] - '0') * (b[j] - '0');
        }
    }
    std::string ans;
    // 从低位到高位处理进位
    for (int i = a_l + b_l - 2; i >= 1; i--) {
        if (res[i] >= 10) {
            res[i - 1] += res[i] / 10;  // 向前进位
            res[i] %= 10;               // 保留个位数字
        }
        ans = std::to_string(res[i]) + ans;  // 拼接到结果前
    }
    // 处理最高位（如果有）
    if (res[0] > 0) {
        ans = std::to_string(res[0]) + ans;
    }
    return ans;
}

// 高精度加法：计算两个大整数的和
std::string big_sum(std::string a, std::string b) {
    std::string res = "";
    int n = a.size(), m = b.size();
    int len = std::max(n, m);
    // 反转字符串，方便从低位（个位）开始相加
    std::reverse(a.begin(), a.end());
    std::reverse(b.begin(), b.end());
    int carry = 0;  // 进位标志
    for (int i = 0; i < len; i++) {
        int cura = (i < n) ? a[i] - '0' : 0;  // 若该位没有数字，则用0补齐
        int curb = (i < m) ? b[i] - '0' : 0;
        int tmp = cura + curb + carry;    // 计算当前位的和加上进位
        res += std::to_string(tmp % 10);  // 当前位只保留个位
        carry = tmp / 10;                 // 计算新的进位
    }
    // 如果最后还有进位，需要补上
    if (carry > 0) {
        res += std::to_string(carry);
    }
    // 因是从低位往高位加的，最后需将结果字符串反转过来
    std::reverse(res.begin(), res.end());
    return res;
}

int main() {
    int n;
    std::cin >> n;  // 读取输入 n

    // multiplier 用于储存当前项的阶乘（初始为 1! = 1）
    std::string multiplier = "1";
    // ans 用于储存阶乘的累加和（初始为 1! 的和）
    std::string ans = "1";

    // 从 2 开始，一直到 n，累加每一项的阶乘
    for (int i = 2; i <= n; i++) {
        // 计算当前项 i!，即 i! = (i-1)! * i
        multiplier = big_multi(multiplier, std::to_string(i));
        // 将 i! 累加到最终结果 ans 中
        ans = big_sum(ans, multiplier);
    }

    // 输出总和 S = 1! + 2! + 3! + ... + n!
    std::cout << ans << std::endl;
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号