简述
在进行计算的过程中，常需要用到极大的整数，例如几百万位的大整数之间的加减乘除的运算。而C++等语言中，能够存储的数据范围是有限的。
int: $-2^{31}$到$2^{31} - 1$ long long: $-2^{63}$到$2^{63} - 1$
当输入数据在此范围内，通过定义变量即可完成。 而当输入数据大于此范围，要怎么做呢？
高精度算法应运而生。涉及加，减，乘，除，乘方，取模，开方等运算。对于一般情况下的高精度算法，可以看做对数字计算过程的模拟：竖式计算。
高精度加法
当进行加法运算的数字较大时，受存储范围限制，无法使用int或long long型变量进行存储。
考虑到加法运算的本质，不妨将数字拆开来存储。
对于一个超过变量存储数据范围的数字，可以将这个数字拆开，拆成一位一位的，或者是几位几位的存储到一个数组中， 用一个数组去表示一个数字。
计算$123+734$
1 2 3
+ 7 3 4
--------
8 5 7
采用以下形式进行存储。
int a[4] = {1, 2, 3};
int b[4] = {7, 3, 4};
int ans[4];
显而易见，$a[\,]$数组每一位分别表示数字$123$的每一位:
a[0]=1,a[1]=2,a[2]=3
$b[\,]$数组分别对应$734$。
则两数相加结果的每一位即为$a[\,]$数组和$b[\,]$数组逐位相加，结果储存在$ans[\,]$数组内。
对于用于记录答案的数组$ans[4]$：
for (int i = 0; i < 3; ++i)
ans[i] = a[i] + b[i];
输出答案：
for (int i = 0; i < 3; ++i)
printf("%d", ans[i]);
以上算法看起来能解决大整数加法运算问题，但并不完整，考虑以下问题
如何得到数字长度？
在进行若干次大整数加法的过程中，所有的大整数需要预处理存入数
组，那么在进行计算时，如何获得数字长度？
采用结构体存储
struct BigNum {
int num[500], len;
};
- num[]数组大小根据数据范围调整
- len表示大整数长度
然而采用用上述存储数据方式，会有一个问题：最高位进位变得很困难。最高位在$num[0]$，所以一旦有进位，需要将$num[\,]$数组中每一位都往后移，时间复杂度为$O(len)$。
解决方案：
倒序存储： $num[\,]$数组从0到len-1依次存储整数个位到最高位。则最高位进位时，只需要$num[len++]=t$，$t$为最高位数字。
计算$578+723$
注意到这里的每一位都有进位
方法一：设一个变量$t$，记录当前进位。
int t = 0;
BigNum a, b, ans;
a.num[0] = 8, a.num[1] = 7, a.num[2] = 5, a.len = 3;
a.num[0] = 3, a.num[1] = 3, a.num[2] = 7, a.len = 3;
ans.len = 3;
for (int i = 0; i < ans.len; ++i) {
ans.num[i] = a.num[i] + b.num[i] + t;
if (ans.num[i] > 9) {
t = ans.num[i] / 10;
ans.num[i] %= 10;
}
else t = 0;
}
if (t) ans.num[ans.len++] = t;
for (int i = ans.len - 1; i >= 0; --i) printf("%d", ans.num[i]);
方法二：
显而易见：边计算边进位和逐位相加不进位最后再统一进位效果是一样的如下，先进行一遍逐位相加。
然后，从$0$开始遍历一遍$ans.num[\,]$，将本位大于$9$的部分进位给更高位。
最后判断是否最高位有进位，有则$ans.len++$
int t = 0;
BigNum a, b, ans;
a.num[0] = 8, a.num[1] = 7, a.num[2] = 5, a.len = 3;
a.num[0] = 3, a.num[1] = 3, a.num[2] = 7, a.len = 3;
ans.len = 3;
for (int i = 0; i < ans.len; ++i) ans.num[i] = a.num[i]+ b.num[i];
for (int i = 0; i < ans.len; ++i) {
if (ans.num[i] > 9) {
ans.num[i + 1]++;
ans.num[i] -= 10;
}
}
if (ans.num[ans.len]) ans.len++;
for (int i = ans.len - 1; i >= 0; --i) printf("%d", ans.num[i]);
实例
A+B Problem
输入两个正整数$A$、$B$，输出$A+B$的值。不用考虑负数 保证$A$、$B$位数小于$500$。
Solution
- 以字符串形式读入数字，并逐位转换成数字倒序存储；
- 进行高精度加法计算；
- 倒序输出。
代码实现
#include <bits/stdc++.h>
using namespace std;
char str[505];
struct BigNum {
int num[505], len;
}A, B, C;
void print(BigNum &x) { //输出大整数x
for(int i = x.len - 1; i >= 0; i--) printf("%d", x.num[i]);
printf("\n");
}
void add(BigNum &x, BigNum &y, BigNum &z) {
z.len = max(x.len, y.len); // 结果最小长度为两者长度最大值
for(int i = 0; i < z.len; i++) z.num[i] = x.num[i] + y.num[i]; // 不进位加法得到初步结果
for(int i = 0; i < z.len; i++)
if(z.num[i] > 9) { // 进行逐位进位
z.num[i + 1] += 1;
z.num[i] -= 10;
}
if(z.num[z.len]) ++z.len; // 判断最高位是否有进位
}
int main() {
// 读取并倒序存储大整数A
scanf("%s", str);
int len = strlen(str);
A.len = len;
for(int i = 0; i < len; i++) A.num[len - i - 1] = str[i] - '0';
// 读取并倒序存储大整数B
scanf("%s", str);
B.len = len = strlen(str);
for(int i = 0; i < len; i++) B.num[len - i - 1] = str[i] - '0';
add(A, B, C); // 计算结果
print(C); // 输出
return 0;
}
高精度减法
实例
A-B Problem
输入两个整数$A$, $B$（第二个可能比第一个大），输出$A-B$的结果。保证$A$、$B$位数小于$10000$。
Solution
- 判断正负
- 基本和加法一模一样，只不过从进位变成退位
- 退位后更新结果长度
代码实现
#include <bits/stdc++.h>
#define MAXN 11111
using namespace std;
char str[MAXN];
struct BigNum {
int num[MAXN], len;
}A, B, C;
void print(BigNum &x) { //输出大整数x
for(int i = x.len - 1; i >= 0; i--) printf("%d", x.num[i]);
printf("\n");
}
int judge(BigNum &x, BigNum &y) {
// 比较函数 长度长的大，其次从高到低逐位比较，全相同返回0，x>y返回1, x<y返回-1
if(x.len > y.len) return 1;
if(x.len < y.len) return -1;
for(int i = x.len - 1; i >= 0; i--) {
if(x.num[i] > y.num[i]) return 1;
if(x.num[i] < y.num[i]) return -1;
}
return 0;
}
void Minus(BigNum &x, BigNum &y, BigNum &z) {
if(judge(x, y) == -1) {
printf("-");
Minus(y, x, z); //保证被减数为较大的
} else {
z.len = x.len; // 结果最小长度为x长度
for(int i = 0; i < z.len; i++) z.num[i] = x.num[i] - y.num[i]; // 不进位减法得到初步结果
for(int i = 0; i < z.len; i++)
if(z.num[i] < 0) { // 进行逐位退位
z.num[i + 1] -= 1;
z.num[i] += 10;
}
while(z.len > 1 && !z.num[z.len - 1]) --z.len; // 判断最高位是否有退位
}
return ;
}
int main() {
// 读取并倒序存储大整数A
scanf("%s", str);
int len = strlen(str);
A.len = len;
for(int i = 0; i < len; i++) A.num[len - i - 1] = str[i] - '0';
// 读取并倒序存储大整数B
scanf("%s", str);
B.len = len = strlen(str);
for(int i = 0; i < len; i++) B.num[len - i - 1] = str[i] - '0';
Minus(A, B, C); // 计算结果
print(C); // 输出
return 0;
}
高精度乘法
高精乘低精
将加法运算改为乘法运算即可。
注意：
- 进位的运算
- 最高位进位的处理，可能不止进一位
代码实现
#include <bits/stdc++.h>
#define MAXN 11111
using namespace std;
char str[MAXN];
struct BigNum {
int num[MAXN], len;
}A, B, C;
void print(BigNum &x) { //输出大整数x
for(int i = x.len - 1; i >= 0; i--) printf("%d", x.num[i]);
printf("\n");
}
void Multi(BigNum &x, int y, BigNum &z) {
z.len = x.len; // 最小长度
for(int i = 0; i < z.len; i++) z.num[i] = x.num[i] * y; //逐位相乘
for(int i = 0; i < z.len; i++) { // 进位处理
z.num[i + 1] += z.num[i] / 10;
z.num[i] %= 10;
if(i == z.len - 1 && z.num[i + 1]) ++z.len; // 最高位进位
}
return ;
}
int main() {
// 读取并倒序存储大整数A
scanf("%s", str);
int len = strlen(str);
A.len = len;
for(int i = 0; i < len; i++) A.num[len - i - 1] = str[i] - '0';
int b;
scanf("%d", &b);
Multi(A, b, C); // 计算结果
print(C); // 输出
return 0;
}
高精乘高精
$132 * 32$
2 1 0 // 在num[]中的下标
---------
1 2 3 // a.num[]
* 3 2 // b.num[]
---------
2 4 6
+3 6 9
---------
3 9 3 6 // ans.num[]
易发现：
乘法竖式中，$a.num[i]$和$b.num[j]$相乘的结果，放在了$ans.num[i+j]$的位置。
$a,b$都为正整数时，长度为$a.len$和$b.len$的数字相乘得到$ans$，则
a.len + b.len - 1 <= ans.len <= a.len + b.len
模拟上例竖式运算过程即可。
代码实现
#include <bits/stdc++.h>
#define MAXN 11111
using namespace std;
char str[MAXN];
struct BigNum {
int num[MAXN], len;
}A, B, C;
void print(BigNum &x) { //输出大整数x
for(int i = x.len - 1; i >= 0; i--) printf("%d", x.num[i]);
printf("\n");
}
void Multi(BigNum &x, BigNum &y, BigNum &z) {
z.len = x.len + y.len; // 最大长度
for(int i = 0; i < x.len; i++)
for(int j = 0; j < y.len; j++) // 模拟乘法竖式
z.num[i + j] += x.num[i] * y.num[j];
for(int i = 0; i < z.len; i++) { // 进位处理
z.num[i + 1] += z.num[i] / 10;
z.num[i] %= 10;
}
while(z.len > 1 && !z.num[z.len - 1]) --z.len;
return ;
}
int main() {
// 读取并倒序存储大整数A
scanf("%s", str);
int len = strlen(str);
A.len = len;
for(int i = 0; i < len; i++) A.num[len - i - 1] = str[i] - '0';
// 读取并倒序存储大整数B
scanf("%s", str);
B.len = len = strlen(str);
for(int i = 0; i < len; i++) B.num[len - i - 1] = str[i] - '0';
Multi(A, B, C); // 计算结果
print(C); // 输出
return 0;
}
版本二：
#include <iostream>
using namespace std;
int a[2010], b[2010], c[4010];
int main() {
string num1, num2;
cin >> num1 >> num2;
int lena = num1.size();
int lenb = num2.size();
// Part 1: 读入字符串后，倒序放入数组中
for (int i = 0; i < lena; ++i) a[i] = num1[lena - i - 1] - '0';
for (int i = 0; i < lenb; ++i) b[i] = num2[lenb - i - 1] - '0';
// Part 2
int lenc = lena + lenb - 1;
for (int i = 0; i < lena; ++i)
for (int j = 0; j < lenb; ++j)
c[i + j] += a[i] * b[j];
// Part 3: 考虑进位
for (int i = 1; i < lenc; ++i) {
c[i] += c[i - 1] / 10;
c[i - 1] %= 10;
}
// part 4: 考虑最高位的进位
while (c[lenc - 1] >= 10) {
c[lenc] = c[lenc - 1] / 10;
c[lenc - 1] %= 10;
lenc++;
}
// 去掉前导0
while (c[lenc - 1] == 0 && lenc > 1) lenc--;
for (int i = lenc - 1; i >= 0; --i) cout << c[i];
cout << '\n';
return 0;
}
高精度除法
高精除以高精
除法是从高位到低位进行运算的。使用一个临时变量来记录余数，注意细节。
计算$2835/27$
1 0 5
27 |----------
|2 8 3 5
|2 7
----------
1 3 5
1 3 5
----------
0
代码实现
#include <bits/stdc++.h>
#define MAXN 11111
using namespace std;
char str[MAXN];
struct BigNum {
int num[MAXN], len;
}A, B, C;
void print(BigNum &x) { //输出大整数x
for(int i = x.len - 1; i >= 0; i--) printf("%d", x.num[i]);
printf("\n");
}
void Div(BigNum &x, int y, BigNum &z) {
z.len = x.len; // 初始长度
int t = 0;
for(int i = z.len - 1; i >= 0; i--) {
t = t * 10 + x.num[i]; // 当前位数字等于上一位余数乘10再加上当前位数字
z.num[i] = t / y; // 除法
t %= y; // 更新t
}
while(z.len > 1 && !z.num[z.len - 1]) --z.len; //去除前导0
return ;
}
int main() {
// 读取并倒序存储大整数A
scanf("%s", str);
int len = strlen(str);
A.len = len;
for(int i = 0; i < len; i++) A.num[len - i - 1] = str[i] - '0';
int y;
scanf("%d", &y);
Div(A, y, C); // 计算结果
print(C); // 输出
return 0;
}
高精除以高精
高精除看起来很复杂，实际上就是一个对位相减的过程。 每次取长度相同的串。
如果除数小于被除数的当前串那么此串尾部就向后移动，直到被除数的当前串大于除数。在实际操作中可以用减法来模拟这个过程 每减一次就在对应除数尾部答案处加一来统计答案。
还是举个例子：看上式，$27$在$28$处查看发现我比$28$小！那么进行一次减法操作使得$2 8 - 2 7$现在被除数 变成$1 3 5$。
1 0 5
27 |----------
|2 8 3 5
|2 7
----------
1 3 5
1 3 5
----------
0
再次查看时发现$27$比$1$要大了，此时不能再减，则将除数$(2 7)$的指针向后移，到了$1 3$的位置，发现还是小，指 针再向后移动。 到了$3 5$处，统计从头到指针的数字(即$0 1 3 5$)与除数($2 7$)进行比较，发现可以操作，那么 就进行减法操作。
每次减完后都检查是否能继续减下去，然后ans[tail]++统计答案tail即是尾指针。
代码实现
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define tail head+len2-1//与head联动的tail 记录除数的尾部指针
#define Init len1=strlen(s1+1),len2=strlen(s2+1);//初始化
const int Maxn=10001;
int len1,len2,cur=1;
char s1[Maxn],s2[Maxn];
int a[Maxn],b[Maxn],c[Maxn],ans[Maxn];
bool compare(int head)
{
cur=1;while(a[cur]==0)cur++;//去除a前面的0 便于计算
if(tail-cur+1 > len2)return 1;//tail-cur+1即是当前串的长度
if(tail-cur+1 < len2)return 0;
string str1="",str2="";//比大小
for(int i=cur;i<=tail;i++){
str1 += a[i]+48;
str2 += b[i-head+1]+48;
}
if(str1>=str2)return 1;//使用重载过的String类比较
else return 0;//如果大于等于就减 小于则不能减
}
int sub(int head)
{
for(int i=tail;i>=tail-len2+1;i--){//从后往前减
a[i]=a[i]-b[i-head+1];//减法
if(a[i]<0){//如果不够减借一位
a[i]+=10;
a[i-1]--;
}
}
ans[tail]++;//统计答案
}
int main()
{
scanf("%s%s",s1+1,s2+1);Init//读入并处理出长度
for(int i=1;i<=len1;i++)a[i] = s1[i]-'0';//读入
for(int i=1;i<=len2;i++)b[i] = s2[i]-'0';//读入
for(int head=1;tail<=len1;head++){//查看该数放在哪一个位置
if( !compare(head) )continue;//如果a小于b 则继续下一层 即把b数往后挪一位
else while( compare(head) ) sub(head);//只要能减就一直减 直到a小于b 同时在tail处统计答案
}
cur=1;while( ans[cur]==0 && cur!=len1 )cur++;//去除前面的0
for(int i=cur;i<=len1;i++)printf("%d",ans[i]);//输出
}
总述
高精度算法一般是固定的模板。
一般情况下没有题目单独考察高精度算法，往往搭配其他算法出现。
故只需要对高精度的模板掌握熟练即可。
一些练习题
1、 麦森数 （ 参考代码 ）
2、 A+B Problem（高精）
3、 A*B Problem
4、 阶乘之和
5、 最大乘积
6、 除以13
7、 国王游戏
8、 循环
9、 矩阵取数游戏
10、数楼梯
%%%