资讯详情

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\)。

【其他说明】

注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 \(n \le 20\)，使用书中的代码无法通过本题。

如果希望通过本题，请继续学习第八章高精度的知识。

---

这道题在类型上属于 高精度乘法 + 高精度加法的综合应用。

题目大意

计算 \(S = 1! + 2! + 3! + \dots + n!\)，其中 \(n \le 50\)，阶乘结果远超 64 位整数范围，必须手写高精度。

特征	说明
题型分类	高精度加法 + 高精度乘法的综合应用
核心知识点	① 高精度乘低精度（阶乘用） ② 高精度加高精度（求和用）
与 P1303 的区别	P1303 是高精度 × 高精度；本题阶乘只需高精度 × 低精度（乘数 ≤ 50），逻辑更简单

因为乘数 i（2~50）始终是普通整数，所以乘法时逐位乘 int 加进位即可，不用嵌套双循环，这也是本题与 P1601 加法模版结合的最佳切入点。

解决思路

1. 拆成两个步骤：

   • 高精度乘低精度：计算当前 i 的阶乘 fact = fact × i
   • 高精度加高精度：sum = sum + fact

2. 数组倒序存储（低位在前）：

   • a[0] 是个位，a[1] 是十位，以此类推。

3. 具体流程：

   • 初始化 a[] 和 sum[] 均为 1（即 1!）。
   • 从 i = 2 到 n：
     • 调用高精度乘低精度，把 i 乘进 a[]。
     • 调用高精度加高精度，把 a[] 累加到 sum[]。
   • 去掉前导零，逆序输出 sum[]。

方法一：基础高精度（数组模拟，通俗易懂）

#include <iostream>
using namespace std;const int MAXN = 2000;  // 50! 约 65 位，2000 很安全
int a[MAXN];            // 存放当前阶乘
int sum[MAXN];          // 存放最终和// 高精度 × 低精度
void mul(int a[], int x) {int carry = 0;for (int i = 0; i < MAXN; ++i) {carry += a[i] * x;a[i] = carry % 10;carry /= 10;}
}// 高精度 + 高精度
void add(int sum[], int a[]) {int carry = 0;for (int i = 0; i < MAXN; ++i) {carry += sum[i] + a[i];sum[i] = carry % 10;carry /= 10;}
}int main() {int n;cin >> n;a[0] = 1;sum[0] = 1;for (int i = 2; i <= n; ++i) {mul(a, i);add(sum, a);}// 逆序输出int p = MAXN - 1;while (p > 0 && sum[p] == 0) --p;for (int i = p; i >= 0; --i)cout << sum[i];cout << endl;return 0;
}

方法二：vector 版本（更安全，方便复用）

#include <iostream>
#include <vector>
using namespace std;// 高精度 × 低精度
vector<int> mul(const vector<int>& A, int b) {vector<int> C;int carry = 0;for (size_t i = 0; i < A.size(); ++i) {carry += A[i] * b;C.push_back(carry % 10);carry /= 10;}while (carry) {C.push_back(carry % 10);carry /= 10;}return C;
}// 高精度 + 高精度
vector<int> add(const vector<int>& A, const vector<int>& B) {vector<int> C;int carry = 0;size_t i = 0;while (i < A.size() || i < B.size() || carry) {int x = (i < A.size() ? A[i] : 0);int y = (i < B.size() ? B[i] : 0);carry += x + y;C.push_back(carry % 10);carry /= 10;++i;}return C;
}int main() {int n;cin >> n;vector<int> fact = {1};   // 当前阶乘vector<int> sum  = {1};   // 累加和for (int i = 2; i <= n; ++i) {fact = mul(fact, i);sum  = add(sum, fact);}// 逆序输出for (int i = sum.size() - 1; i >= 0; --i)cout << sum[i];cout << endl;return 0;
}

---

Python 版本

Python 自带大整数，直接硬算就能 AC。但手写结构可以帮助理解思路。

def mul(A, x):C = []carry = 0for a in A:carry += a * xC.append(carry % 10)carry //= 10while carry:C.append(carry % 10)carry //= 10return Cdef add(A, B):C = []i = carry = 0while i < len(A) or i < len(B) or carry:x = A[i] if i < len(A) else 0y = B[i] if i < len(B) else 0carry += x + yC.append(carry % 10)carry //= 10i += 1return Cn = int(input())
fact = [1]
s = [1]
for i in range(2, n + 1):fact = mul(fact, i)s = add(s, fact)
print(''.join(str(x) for x in reversed(s)))

总结

内容	说明
题目类型	高精度加法 + 高精度乘法的综合应用
乘法特征	高精度 × 低精度（乘数 ≤ 50），比 P1303 的大数相乘简单
加法特征	与 P1601 逻辑完全一致，只多一个累加循环
核心优化	边乘边进位，处理好进位链
学习价值	高精度四则运算的综合性练习