笔记·高精度算法
2026-06-29 18:39:35
发布于：云南
23阅读
0回复
0点赞
高精度算法
一、什么是高精度算法
C++中的int最大约21亿，long long最大约9.22×10¹⁸。当需要计算远超这个范围的数（比如100位的数字）时，普通数据类型存不下。高精度算法的核心思想是：用数组的每个元素存储大数的一位数字，然后模拟人工手算的过程进行运算。
通常我们用字符串读入大数，逆序存入数组（个位放在下标1，十位放在下标2……这样方便进位）。
二、高精度加法
原理：从个位开始逐位相加，满10进1。比如123+456，个位3+6=9，十位2+5=7，百位1+4=5，结果是579。
步骤：
- 用字符串读入两个大数
- 逆序存入整型数组
- 从低位到高位逐位相加并处理进位
- 逆序输出结果
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN];
char s1[MAXN],s2[MAXN];
int main() {
scanf("%s %s",s1,s2);
int l1=strlen(s1),l2=strlen(s2);
for(int i=1;i<=l1;i++) {
a[i]=s1[l1-i]-'0';
}
for(int i=1;i<=l2;i++) {
b[i]=s2[l2-i]-'0';
}
int len=max(l1,l2);
for(int i=1;i<=len;i++) {
c[i]+=a[i]+b[i];
if(c[i]>=10) {
c[i]-=10;
c[i+1]++;
}
}
if(c[len+1]>0) len++;
for(int i=len;i>=1;i--) {
printf("%d",c[i]);
}
printf("\n");
return 0;
}
三、高精度减法
原理：从个位开始逐位相减，如果被减数某位小于减数对应位，就向高位借1当10。
步骤：
- 先比较两个数的大小，确保大数减小数（如果结果是负数，记录符号）
- 逆序存入数组
- 逐位相减，不够就借位
- 去除前导零后输出
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN];
char s1[MAXN],s2[MAXN];
int cmp(char x[],char y[]) {
int lx=strlen(x),ly=strlen(y);
if(lx!=ly) return lx>ly;
for(int i=0;i<lx;i++) {
if(x[i]!=y[i]) return x[i]>y[i];
}
return 1;
}
int main() {
scanf("%s %s",s1,s2);
int sign=1;
if(!cmp(s1,s2)) {
sign=-1;
swap(s1,s2);
}
int l1=strlen(s1),l2=strlen(s2);
for(int i=1;i<=l1;i++) {
a[i]=s1[l1-i]-'0';
}
for(int i=1;i<=l2;i++) {
b[i]=s2[l2-i]-'0';
}
int len=l1;
for(int i=1;i<=len;i++) {
if(a[i]<b[i]) {
a[i]+=10;
a[i+1]--;
}
c[i]=a[i]-b[i];
}
while(len>1&&c[len]==0) len--;
if(sign==-1) printf("-");
for(int i=len;i>=1;i--) {
printf("%d",c[i]);
}
printf("\n");
return 0;
}
四、高精度乘法
原理：模拟竖式乘法。a的第i位乘以b的第j位，结果应累加到c的第i+j-1位。比如123×45，3×5=15放在第1位，3×4=12放在第2位，2×5=10放在第2位……最后统一进位。
步骤：
- 逆序存入数组
- 双重循环逐位相乘并累加
- 统一处理进位
- 去除前导零后输出
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN*2];
char s1[MAXN],s2[MAXN];
int main() {
scanf("%s %s",s1,s2);
int l1=strlen(s1),l2=strlen(s2);
for(int i=1;i<=l1;i++) {
a[i]=s1[l1-i]-'0';
}
for(int i=1;i<=l2;i++) {
b[i]=s2[l2-i]-'0';
}
for(int i=1;i<=l1;i++) {
for(int j=1;j<=l2;j++) {
c[i+j-1]+=a[i]*b[j];
}
}
int len=l1+l2;
for(int i=1;i<=len;i++) {
if(c[i]>=10) {
c[i+1]+=c[i]/10;
c[i]%=10;
}
}
while(len>1&&c[len]==0) len--;
for(int i=len;i>=1;i--) {
printf("%d",c[i]);
}
printf("\n");
return 0;
}
五、高精度除法（高精除以低精）
原理：从最高位开始逐位处理。每次用上一位的余数乘以10加上当前位，然后除以除数，得到当前位的商，余数留给下一位。
步骤：
- 用字符串存储被除数（不逆序，因为从高位开始处理）
- 从高位到低位逐位计算
- 去除前导零后输出商和余数
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],c[MAXN];
char s[MAXN];
int main() {
int b;
scanf("%s %d",s,&b);
int l=strlen(s);
for(int i=1;i<=l;i++) {
a[i]=s[i-1]-'0';
}
int r=0;
for(int i=1;i<=l;i++) {
int cur=r*10+a[i];
c[i]=cur/b;
r=cur%b;
}
int st=1;
while(st<l&&c[st]==0) st++;
for(int i=st;i<=l;i++) {
printf("%d",c[i]);
}
printf("\n");
printf("%d\n",r);
return 0;
}
六、高精度除法（高精除以高精）
原理：用减法模拟除法。对于每一位，用被除数减去除数，能减多少次，该位商就是多少。为了提升效率，采用倍增思想，每次把除数扩大10倍来试商。
步骤：
- 判断被除数是否小于除数，若是则商0
- 从最高位开始，每次将除数左移（即乘以10的幂次）
- 用被除数不断减去除数，统计次数作为该位商
- 更新被除数，继续下一位
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN],t[MAXN];
char s1[MAXN],s2[MAXN];
int cmpArr(int x[],int y[],int lx,int ly) {
if(lx!=ly) return lx>ly;
for(int i=lx;i>=1;i--) {
if(x[i]!=y[i]) return x[i]>y[i];
}
return 1;
}
void subArr(int x[],int y[],int &len) {
for(int i=1;i<=len;i++) {
if(x[i]<y[i]) {
x[i]+=10;
x[i+1]--;
}
x[i]-=y[i];
}
while(len>1&&x[len]==0) len--;
}
int main() {
scanf("%s %s",s1,s2);
int l1=strlen(s1),l2=strlen(s2);
for(int i=1;i<=l1;i++) {
a[i]=s1[l1-i]-'0';
}
for(int i=1;i<=l2;i++) {
b[i]=s2[l2-i]-'0';
}
if(l1<l2||(l1==l2&&!cmpArr(a,b,l1,l2))) {
printf("0\n");
for(int i=l1;i>=1;i--) printf("%d",a[i]);
printf("\n");
return 0;
}
int ansLen=l1-l2+1;
for(int i=ansLen;i>=1;i--) {
memset(t,0,sizeof(t));
for(int j=1;j<=l2;j++) {
t[i+j-1]=b[j];
}
int tLen=l2+i-1;
while(cmpArr(a,t,l1,tLen)) {
c[i]++;
subArr(a,t,l1);
}
}
while(ansLen>1&&c[ansLen]==0) ansLen--;
for(int i=ansLen;i>=1;i--) printf("%d",c[i]);
printf("\n");
while(l1>1&&a[l1]==0) l1--;
for(int i=l1;i>=1;i--) printf("%d",a[i]);
printf("\n");
return 0;
}
七、总结
| 运算 | 时间复杂度 | 关键点 |
|---|---|---|
| 加法 | O(n) | 逐位相加，处理进位 |
| 减法 | O(n) | 先比较大小，逐位借位 |
| 乘法 | O(n²) | 逐位相乘后统一进位 |
| 除法（低精） | O(n) | 从高位逐位求商 |
| 除法（高精） | O(n²) | 减法模拟，倍增试商 |
高精度算法是算法竞赛中的基础技能，掌握后可以处理任意大的整数运算。实际应用中，通常用加法、减法和乘法较多，除法相对较少，但原理都需要理解透彻。
有帮助，赞一个