高精度问题
高精度问题
一、基本了解
C++ 中普通整数能存多大的数？
- int：大约 ±9e9
- long long：大约 ±9e18
看着很大对不对？
但是！竞赛、算法题里经常出现这种数据：
输入一个 100 位、200 位、1000 位的超大整数，求加法、乘法
比如：
12345678901234567890...（100位）这种数，任何原生整型都存不下，直接爆掉。
解决办法：高精度算法
本质：用字符串 / 数组 手动模拟小学生竖式计算。
高精度就是自己手写加减乘除规则，处理超长整数
核心思想：数字太长存不下，需要拆成一位一位存进数组
计算途中有两位数时，就要模仿竖式手动进位
我们人脑读数：高位在前比如：1234（1是千位，最高位）
但是！高精度代码统一规则：
数组低位存数字低位！反转存储！
示例：数字1234
数组存成：a[0]=4, a[1]=3, a[2]=2, a[3]=1
为什么反转？
因为加减乘都是从个位开始算、往高位进位，低位放前面，下标刚好对齐
二、高精度加法
原理
照搬小学竖式：
- 从个位逐位相加
- 保留个位，剩下的进位给下一位
模板
#include<bits/stdc++.h> using namespace std; const int N=1e5; // 设置数组最大容量，能够存储很长的大数 int a[N],b[N],res[N]; // a[]、b[]存放两个输入大数，res[]存放相加结果，存储规则：低位在前 int main(){ string s1,s2; cin>>s1>>s2; // 用字符串读取超大整数（超过long long范围，不能直接用数字变量存储） int la=s1.size(); // 获取第一个数字字符串的长度 int lb=s2.size(); // 获取第二个数字字符串的长度 // 将字符串转为低位在前的整型数组 // 举例：字符串"1234" → a[0]=4，a[1]=3，a[2]=2，a[3]=1 for(int i=0;i<la;i++){ a[i]=s1[la-1-i]-'0'; } for(int i=0;i<lb;i++){ b[i]=s2[lb-1-i]-'0'; } int t=0; // t用来保存加法进位，初始进位为0 // 模拟竖式加法，循环执行到较长数字的最高位 for(int i=0;i<max(la,lb);i++){ t = t + a[i] + b[i]; // 当前位总和 = 上一轮进位 + a当前数位 + b当前数位 res[i] = t % 10; // 取个位作为结果当前位 t = t / 10; // 十位部分作为新的进位，参与下一位运算 } // 处理输出：结果数组低位在前，需要倒序打印 if(t!=0){ // 循环结束仍有进位，说明多出最高一位 res[max(la,lb)]=t; // 从新增最高位倒序遍历输出 for(int i=max(la,lb);i>=0;i--){ cout<<res[i]; } } else{ // 没有剩余进位，从最长数的末尾向前输出 for(int i=max(la,lb)-1;i>=0;i--){ cout<<res[i]; } } return 0; }三、高精度减法
原理
竖式减法：不够减向前借位
前提：我们默认s1 > s2
模板
#include<bits/stdc++.h> using namespace std; const int N=1e5; int a[N],b[N],res[N]; int main(){ string s1,s2; cin>>s1>>s2; int la=s1.size(); int lb=s2.size(); //字符串转【低位在前】数组 for(int i=0;i<la;i++){ a[i]=s1[la-1-i]-'0'; } for(int i=0;i<lb;i++){ b[i]=s2[lb-1-i]-'0'; } int t=0; //t代表借位，初始0 //逐位相减 for(int i=0;i<la;i++){ // 当前位 = a本位 - b本位 - 上一轮借位 int now = a[i] - b[i] - t; t = 0; //清空本次借位 if(now < 0){ //不够减，需要向前借1 now += 10; t = 1; //标记下一位需要减1 } res[i] = now; } // 去除前导零（例如 1000-999=1，不要输出0001） int len = la; while(len > 1 && res[len-1]==0){ len--; } //逆序输出 for(int i=len-1;i>=0;i--){ cout<<res[i]; } return 0; }四、高精度乘法
原理
小学竖式：每一位乘每一位，错位相加
公式：res[i+j] += a[i] * b[j]
模板
#include<bits/stdc++.h> using namespace std; const int N=1e5; int a[N],b[N],res[N]; int main(){ string s1,s2; cin>>s1>>s2; int la=s1.size(); int lb=s2.size(); // 字符串转【低位在前】数组 for(int i=0;i<la;i++){ a[i] = s1[la-1-i] - '0'; } for(int i=0;i<lb;i++){ b[i] = s2[lb-1-i] - '0'; } // 核心乘法：a第i位 × b第j位，累加至 res[i+j] for(int i=0;i<la;i++){ for(int j=0;j<lb;j++){ res[i+j] += a[i] * b[j]; } } // 统一处理进位 int t=0; // 两个数相乘最多 la+lb 位 for(int i=0;i<la+lb;i++){ t += res[i]; res[i] = t % 10; t /= 10; } // 去除前导零 int len = la + lb; while(len>1 && res[len-1]==0){ len--; } // 逆序输出 for(int i=len-1;i>=0;i--){ cout<<res[i]; } return 0; }位置规律
a[i]代表第 (10^i) 位，b[j]代表 (10^j) 位(10^i *10^j = 10^{i+j})
所以乘积存到
res[i+j]和加法区别
加法：一层循环逐位运算
乘法：两层循环枚举所有数位两两相乘，先累加、最后统一进位
五、核心知识点总结
- 高精度解决的问题：超出 long long 范围的超大整数运算
- 存储方式：字符串读入 → 反转存入数组（低位在前）
- 加法核心：逐位相加、记录进位
- 减法核心：不够减向前借位、去前导零
- 乘法核心：i,j 错位累积、统一处理进位，数组开双倍空间，防止数组越界
- 输出方式：逆序输出数组
六、什么时候用高精度
- 数字位数 ≥ 20 位
- 大数阶乘、大数幂运算
- 超大数加减乘
- 答案数值极大，无法用 long long 存储
七、例题
洛谷P1045麦森数（[P1045NOIP 2003 普及组] 麦森数 - 洛谷）
#include<bits/stdc++.h> using namespace std; int n,a[1000]={0},res[1000]={0}; void mul1(){ int temp[1000]={0}; for(int i=0;i<500;i++){ for(int j=0;j<500;j++){ temp[j+i]=temp[j+i]+res[i]*a[j]; } } int t=0; for(int i=0;i<500;i++){ temp[i]+=t; res[i]=temp[i]%10; t=temp[i]/10; } } void mul2(){ int temp[1000]={0}; for(int i=0;i<500;i++){ for(int j=0;j<500;j++){ temp[i+j]+=a[i]*a[j]; } } int t=0; for(int i=0;i<500;i++){ temp[i]+=t; a[i]=temp[i]%10; t=temp[i]/10; } } void quick_pow(int p){ res[0]=1,a[0]=2; while(p){ if(p&1){ mul1(); } mul2(); p>>=1; } } int main(){ cin>>n; int l=n*log10(2)+1; cout<<l<<endl; quick_pow(n); res[0]-=1; int c=0; for(int i=499;i>=0;i--){ if(c==50){ cout<<endl; c=0; } cout<<res[i]; c++; } return 0; }L-A × B_河南萌新联赛2026第（四）场：南阳理工学院
#include<bits/stdc++.h> using namespace std; #define int long long signed main(){ string a,b; cin>>a>>b; reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); vector<int>res(a.size()+b.size()); for(int i=0;i<a.size();i++){ for(int j=0;j<b.size();j++){ int a1=a[i]-'0'; int b1=b[j]-'0'; res[i+j]=res[i+j]+a1*b1; } } int c=0; for(int i=0;i<res.size();i++){ int sum=res[i]+c; res[i]=sum%10; c=sum/10; } string ans; bool ok=true; for(int i=res.size()-1;i>=0;i--){ if(res[i]==0&&ok){ continue; } ok=false; ans.push_back(res[i]+'0'); } cout<<ans; return 0; }