1. 项目概述：大整数类的实现与应用
洛谷P1009题目要求实现一个大整数类（BigInteger），这是算法竞赛和编程学习中非常经典的题目类型。大整数类主要用于处理超出基本数据类型范围的整数运算，比如计算1000的阶乘这类普通int或long long无法存储的数值。
我在ACM竞赛和日常教学中多次实现过各种版本的大整数类，发现虽然核心思路相似，但在不同应用场景下（如竞赛解题、密码学计算、高精度科学计算）需要针对性地优化。本文将分享一个经过实战检验的实现方案，特别适合算法竞赛使用。
2. 核心设计思路
2.1 存储结构选择
最常用的大整数存储方式是用数组存储每一位数字。我们采用vector 存储，每个元素代表一位十进制数字，低位在前（即数字123存储为[3,2,1]）。这种设计有三大优势：
- 动态扩容方便，不像静态数组需要预设大小
- 低位在前的存储方式便于进位处理
- 十进制表示直观，调试方便
注意：竞赛中如果对性能要求极高，可以考虑使用万进制（每个元素存4位数字）或压位存储，但会增加代码复杂度。
2.2 基础运算算法
2.2.1 加法实现
BigInteger operator+(const BigInteger& other) const { BigInteger result; int carry = 0; size_t max_len = max(digits.size(), other.digits.size()); for(size_t i = 0; i < max_len || carry; ++i) { int sum = carry; if(i < digits.size()) sum += digits[i]; if(i < other.digits.size()) sum += other.digits[i]; result.digits.push_back(sum % 10); carry = sum / 10; } return result; }这个实现的关键点：
- 同时处理两个数的当前位和进位
- 循环继续条件包含carry != 0，确保最高位进位不被遗漏
- 时间复杂度O(max(n,m))，n和m分别是两个数的位数
2.2.2 乘法实现
高精度乘法采用模拟竖式计算的方法，但有个重要优化技巧：先计算再统一处理进位。这样可以减少中间进位的次数，提升效率。
BigInteger operator*(const BigInteger& other) const { BigInteger result; result.digits.resize(digits.size() + other.digits.size(), 0); for(size_t i = 0; i < digits.size(); ++i) { int carry = 0; for(size_t j = 0; j < other.digits.size() || carry; ++j) { long long product = result.digits[i+j] + (long long)digits[i] * (j < other.digits.size() ? other.digits[j] : 0) + carry; result.digits[i+j] = product % 10; carry = product / 10; } } // 去除前导零 while(result.digits.size() > 1 && result.digits.back() == 0) { result.digits.pop_back(); } return result; }2.3 输入输出处理
2.3.1 从字符串构造
BigInteger(const string& s) { digits.resize(s.length()); for(int i = 0; i < s.length(); ++i) { digits[s.length()-1-i] = s[i] - '0'; } removeLeadingZeros(); }2.3.2 输出格式化
string toString() const { string s; for(auto it = digits.rbegin(); it != digits.rend(); ++it) { s += to_string(*it); } return s.empty() ? "0" : s; }3. 性能优化技巧
3.1 内存预分配
在知道大概结果长度的情况下（如乘法结果位数不超过m+n），预先reserve空间可以避免多次扩容：
vector<int> result; result.reserve(m + n); // 乘法结果预分配3.2 运算符重载顺序
对于连续运算如a+b+c，正确的运算符重载顺序可以避免不必要的拷贝：
// 正确写法：返回const引用 const BigInteger& operator+=(const BigInteger& other) { *this = *this + other; return *this; }3.3 快速阶乘算法
针对P1009的阶乘计算，可以采用分段相乘再合并的策略：
- 将1~n的数分成若干组
- 分别计算每组的乘积
- 合并各组结果
这种方法可以利用现代CPU的多核心特性，大幅提升大数阶乘的计算速度。
4. 常见问题与调试技巧
4.1 典型错误排查表
| 问题现象 | 可能原因 | 解决方案 |
|---|---|---|
| 结果少一位 | 最高位进位未处理 | 检查循环条件是否包含carry != 0 |
| 乘法结果错误 | 中间结果溢出 | 使用long long存储中间乘积 |
| 前导零问题 | 构造时未处理 | 添加removeLeadingZeros()方法 |
| 性能低下 | 频繁内存分配 | 预分配足够空间 |
4.2 调试日志输出
在关键运算处添加调试输出：
void debugPrint(const string& msg) const { cerr << msg << ": "; for(auto it = digits.rbegin(); it != digits.rend(); ++it) { cerr << *it; } cerr << endl; }4.3 边界测试用例
必须测试的边界情况：
- 0的阶乘（应该为1）
- 大数乘以0
- 连续进位（如999999+1）
- 前导零的输入（如"00123"）
5. 完整实现示例
以下是经过竞赛验证的完整BigInteger类实现（核心部分）：
class BigInteger { private: vector<int> digits; void removeLeadingZeros() { while(digits.size() > 1 && digits.back() == 0) { digits.pop_back(); } } public: BigInteger() = default; BigInteger(const string& s) { digits.resize(s.length()); for(int i = 0; i < s.length(); ++i) { digits[s.length()-1-i] = s[i] - '0'; } removeLeadingZeros(); } BigInteger operator+(const BigInteger& other) const { BigInteger result; int carry = 0; size_t max_len = max(digits.size(), other.digits.size()); for(size_t i = 0; i < max_len || carry; ++i) { int sum = carry; if(i < digits.size()) sum += digits[i]; if(i < other.digits.size()) sum += other.digits[i]; result.digits.push_back(sum % 10); carry = sum / 10; } return result; } BigInteger operator*(const BigInteger& other) const { BigInteger result; result.digits.resize(digits.size() + other.digits.size(), 0); for(size_t i = 0; i < digits.size(); ++i) { int carry = 0; for(size_t j = 0; j < other.digits.size() || carry; ++j) { long long product = result.digits[i+j] + (long long)digits[i] * (j < other.digits.size() ? other.digits[j] : 0) + carry; result.digits[i+j] = product % 10; carry = product / 10; } } result.removeLeadingZeros(); return result; } string toString() const { string s; for(auto it = digits.rbegin(); it != digits.rend(); ++it) { s += to_string(*it); } return s.empty() ? "0" : s; } };6. 洛谷P1009题解
使用上述BigInteger类解决阶乘求和问题：
#include <iostream> #include <vector> #include <string> using namespace std; // 此处插入上述BigInteger类实现 int main() { int n; cin >> n; BigInteger sum("0"); BigInteger fact("1"); for(int i = 1; i <= n; ++i) { BigInteger multiplier(to_string(i)); fact = fact * multiplier; sum = sum + fact; } cout << sum.toString() << endl; return 0; }这个实现的时间复杂度是O(n^2)，对于n≤50的题目要求完全足够。在实际竞赛中，我建议将BigInteger类预先准备好作为模板，遇到需要高精度运算的题目可以直接使用。
