高精度问题

一、基本了解

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

为什么反转？

因为加减乘都是从个位开始算、往高位进位，低位放前面，下标刚好对齐

二、高精度加法

原理

照搬小学竖式：

1. 从个位逐位相加
2. 保留个位，剩下的进位给下一位

模板

#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]

和加法区别

加法：一层循环逐位运算

乘法：两层循环枚举所有数位两两相乘，先累加、最后统一进位

五、核心知识点总结

1. 高精度解决的问题：超出 long long 范围的超大整数运算
2. 存储方式：字符串读入 → 反转存入数组（低位在前）
3. 加法核心：逐位相加、记录进位
4. 减法核心：不够减向前借位、去前导零
5. 乘法核心：i,j 错位累积、统一处理进位，数组开双倍空间，防止数组越界
6. 输出方式：逆序输出数组

六、什么时候用高精度

• 数字位数 ≥ 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; }