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[ij] (long long)digits[i] * (j other.digits.size() ? other.digits[j] : 0) carry; result.digits[ij] 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 内存预分配在知道大概结果长度的情况下如乘法结果位数不超过mn预先reserve空间可以避免多次扩容vectorint result; result.reserve(m n); // 乘法结果预分配3.2 运算符重载顺序对于连续运算如abc正确的运算符重载顺序可以避免不必要的拷贝// 正确写法返回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连续进位如9999991前导零的输入如001235. 完整实现示例以下是经过竞赛验证的完整BigInteger类实现核心部分class BigInteger { private: vectorint 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[ij] (long long)digits[i] * (j other.digits.size() ? other.digits[j] : 0) carry; result.digits[ij] 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类预先准备好作为模板遇到需要高精度运算的题目可以直接使用。 
长河君 · 2026/10/26 4:38:09 · 阅读 1.2k 大整数类实现与高精度运算优化技巧
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[ij] (long long)digits[i] * (j other.digits.size() ? other.digits[j] : 0) carry; result.digits[ij] 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 内存预分配在知道大概结果长度的情况下如乘法结果位数不超过mn预先reserve空间可以避免多次扩容vectorint result; result.reserve(m n); // 乘法结果预分配3.2 运算符重载顺序对于连续运算如abc正确的运算符重载顺序可以避免不必要的拷贝// 正确写法返回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连续进位如9999991前导零的输入如001235. 完整实现示例以下是经过竞赛验证的完整BigInteger类实现核心部分class BigInteger { private: vectorint 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[ij] (long long)digits[i] * (j other.digits.size() ? other.digits[j] : 0) carry; result.digits[ij] 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类预先准备好作为模板遇到需要高精度运算的题目可以直接使用。