阶乘求和全解析：从 Python 秒过到 C++ 手写高精度

1. 概述

在洛谷刷题时，我偶然点进了一道看起来非常“友善”的题目——P1009 阶乘求和。题面简单得不能再简单，只要求我们计算：

$$S=1!+2!+3!+\cdots +n!（1\le n\le 50）$$

看完题我心里一笑：这不就是个循环累加阶乘的问题？
没有数组处理，没有边界卡点，没有复杂输入输出格式 —— 简直是送分题。

我很快写好了 C++ 代码，自信地提交上去，然后……就没然后了。评测系统直接返回了“答案错误”的提示，而且是多个测试点都挂掉。更离谱的是，程序有时候还会输出一个负数！

这让我顿时陷入沉思：
👉 明明代码逻辑是对的，为什么会错？
👉 到底是哪个环节出了问题？
👉 Python 同样逻辑就能通过，我的 C++ 到底差在哪？

于是我开始查资料、调试，最后发现问题出在 C++ 的整数精度限制上 —— 当 n 变大时，阶乘的值远远超出了 long long 能表示的范围，导致了溢出错误。

这次“看似简单”的翻车经历，也让我深入了解了高精度计算在刷题中的重要性，也顺便复习了一遍 Python 和 C++ 在处理大数时的差异和各自优势。

本文就以这道题为例，先介绍常规思路，再分析为什么它在 C++ 中会失败，然后提供两种可行的解决方案：

• ✅ 用 Python，借助其原生支持的任意精度整数，轻松 AC；
• ✅ 用 C++，手写高精度加法与乘法，真正掌握底层实现。

无论你是追求快速 AC，还是提升算法功底，这篇文章都希望能对你有所启发。

2. 常规 C++ 解法

我们都知道阶乘的基本实现方式非常简单，一个循环搞定：

#include<iostream>
using namespace std;

long long accumulate_jc(int num){
    long long ans = 1;
    for(int i = 1; i <= num; i++){
        ans *= i;
    }
    return ans;
}

int main(){
    int n;
    cin >> n;
    long long sum = 0;
    for(int i = 1; i <= n; i++){
        sum += accumulate_jc(i);
    }
    cout << sum << endl;
    return 0;
}

这个程序在 n=3 时输出 1!+2!+3!=1+2+6=9，结果没问题。可是当提交到洛谷的测评系统，在 n=50 时就不对劲了：结果错误，甚至出现负数！

3. 错误原因

long long 在 C++ 中的最大值约为 $9.2\times 10^{18}$，而 50! 的值约为：

$$50!\approx 3.04\times 10^{64}$$

这远远超出了 long long 能表示的范围！因此，整数溢出 就成了导致程序错误的根本原因。

4. 用 Python 轻松应对（自动高精度）

你可能已经想到：Python 是不是能解决这个问题？答案是：完全可以！

def accumulate_jc(num):
    ans = 1
    for i in range(1, num+1):
        ans *= i
    return ans

n = int(input())
total = 0
for i in range(1, n+1):
    total += accumulate_jc(i)
print(total)

为什么 Python 能轻松跑通？

因为 Python 的 int 类型本质上是任意精度整数，当数字变大时，底层会自动扩展位数，直到内存上限。

所以在处理高精度问题时，Python 是“作弊般”的存在，用起来很爽。

5. 解法二：C++ 高精度加法与乘法

如果你仍然坚持用 C++，那就必须自己实现高精度整数的加法与乘法。

5.1 思路简述

• 用 vector<int> 存储大整数的每一位（低位在前，高位在后）；
• 手动实现乘法（大整数 × 整数）和加法（两个大整数相加）；
• 循环计算每个阶乘，并用高精度累加到最终结果中。

5.2 高精度 C++ 实现代码

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

// 高精度乘法：a × b（a 为 vector 表示的大数）
vector<int> multiply(vector<int>& a, int b) {
    vector<int> res;
    int carry = 0;
    for (int i = 0; i < a.size(); i++) {
        int temp = a[i] * b + carry;
        res.push_back(temp % 10);
        carry = temp / 10;
    }
    while (carry) {
        res.push_back(carry % 10);
        carry /= 10;
    }
    return res;
}

// 高精度加法：a + b
vector<int> add(vector<int>& a, vector<int>& b) {
    vector<int> res;
    int carry = 0;
    int n = max(a.size(), b.size());
    for (int i = 0; i < n; i++) {
        int x = i < a.size() ? a[i] : 0;
        int y = i < b.size() ? b[i] : 0;
        int sum = x + y + carry;
        res.push_back(sum % 10);
        carry = sum / 10;
    }
    if (carry) res.push_back(carry);
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> sum = {0}; // 初始结果为 0

    for (int i = 1; i <= n; i++) {
        vector<int> fac = {1}; // 初始化阶乘为 1
        for (int j = 2; j <= i; j++) {
            fac = multiply(fac, j); // fac *= j
        }
        sum = add(sum, fac); // sum += fac
    }

    // 逆序输出结果（高位在前）
    for (int i = sum.size() - 1; i >= 0; i--) {
        cout << sum[i];
    }
    cout << endl;
    return 0;
}

这次“翻车”让我深刻意识到：刷题过程中踩坑才是最好的学习机会。

6. 相似题目推荐

如果你在解决这类高精度问题的过程中觉得意犹未尽，或者希望继续练习相关技巧，LeetCode 上也有不少非常典型的高精度模拟题目可以作为延伸练习。

这些题虽然看起来是“字符串处理”或者“链表处理”，但本质上考察的依然是模拟大整数的加法、乘法逻辑，与本文中的高精度思路一脉相承：

• 字符串相加
  👉 Add Strings（字符串相加）

  给定两个表示非负整数的字符串，返回它们的和。需要模拟竖式加法，不可使用内建高精度库。

• 字符串相乘
  👉 Multiply Strings（字符串相乘）

  两个超大整数的乘法模拟，经典的高精度乘法题。完全不能用内置大整数库，必须手写处理进位和位数。

• 两数相加
  👉 Add Two Numbers（两数相加）

  使用链表按位表示两个非负整数，返回它们的和。考察链表处理+进位逻辑，适合作为高精度入门题。

• 从“字符串相加”入手，掌握进位加法；

• 再尝试“字符串相乘”，挑战进位乘法和模拟乘法竖式计算；

• 最后试试“链表加法”，理解数据结构 + 高精度结合的题型。

如果你已经掌握了本文的高精度思路，尝试用 C++ 手动实现这些 LeetCode 题，也是一种非常不错的算法训练路径。高精度计算虽然繁琐，但能极大提升你对“模拟类题目”的掌控力，尤其在比赛、面试或笔试中，这类题型可谓常客。