算法学习——高精度加减乘除

当数据的值特别大，各种类型都存不下的时候，此时就要用高精度算法来计算加减乘除：

• 先用字符串读入这个数，然后用数组逆序存储该数的每一位；
• 利用数组，模拟加减乘除运算的过程。

高精度算法本质上还是模拟算法，用代码模拟小学列竖式计算加减乘除的过程。

一、高精度加法

P1601 高精度加法

题目背景

本题是高精度加法的模板题。

题目描述

给定两个非负整数 $a,b$，求它们的和。不用考虑负数。

输入格式

输入共两行，每行一个非负整数，分别为 $a,b$。

输出格式

输出一行一个非负整数，表示 $a+b$ 的值。

输入输出样例 #1

输入 #1

1
1

输出 #1

2

输入输出样例 #2

输入 #2

1001
9099

输出 #2

10100

说明/提示

对于 $20\%$ 的测试数据，$a,b\le 10^9$；
对于 $40\%$ 的测试数据，$a,b\le 10^{18}$；
对于 $100\%$ 的测试数据，$0\le a,b\le 10^{500}$。

解法

模拟小学「列竖式」计算「两数相加」的过程。

处理结果的位数。

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc;
// 高精度加法的模板 c = a + b
void add(int c[], int a[], int b[])
{
for(int i = 0; i < lc; ++i)
{
// 对应位相加, 再加上进位
c[i] += a[i] + b[i];
// 处理进位
c[i + 1] += c[i] / 10;
// 处理余数
c[i] %= 10;
}
if(c[lc]) ++lc;
}
int main()
{
string x, y;
cin >> x >> y;
la = x.size(), lb = y.size(), lc = max(la, lb);
// 拆分每一位逆序放在数组中
for(int i = 0; i < la; ++i) a[la – 1 – i] = x[i] – '0';
for(int i = 0; i < lb; ++i) b[lb – 1 – i] = y[i] – '0';
add(c, a, b);
for(int i = lc – 1; i >= 0; —i) cout << c[i];
return 0;
}

二、高精度减法

P2142 高精度减法

题目描述

给定两个正整数 $a,b$，求 $a-b$ 的值。

输入格式

输入共两行，每行一个正整数，分别为 $a,b$。

输出格式

输出一行一个整数，表示 $a-b$ 的值。

如果 $a-b<0$，请输出负号。

输入输出样例 #1

输入 #1

2
1

输出 #1

1

说明/提示

对于 $20\%$ 的数据，$a,b$ 在long long类型的存储范围内；
对于 $100\%$ 的数据，$0<a,b\le 10^{10086}$。

解法

模拟小学「列竖式」计算「两数相减」的过程。

处理前导零。

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc;
bool cmp(string& x, string& y)
{
// 先比较长度
if(x.size() != y.size()) return x.size() < y.size();
// 再按照字典序的方式比较
return x < y;
}
// 高精度减法的模板 c = a – b
void sub(int c[], int a[], int b[])
{
for(int i = 0; i < lc; ++i)
{
// 对应位相减, 然后处理借位
c[i] += a[i] – b[i];
if(c[i] < 0)
{
c[i + 1] -= 1; // 借位
c[i] += 10;
}
}
// 处理前导零
while(lc > 1 && c[lc – 1] == 0) lc—;
}
int main()
{
string x, y;
cin >> x >> y;
if(cmp(x, y))
{
swap(x, y);
cout << '-';
}
la = x.size(), lb = y.size(), lc = max(la, lb);
for(int i = 0; i < la; ++i) a[la – i – 1] = x[i] – '0';
for(int i = 0; i < lb; ++i) b[lb – i – 1] = y[i] – '0';
sub(c, a, b);
for(int i = lc – 1; i >= 0; —i) cout << c[i];
return 0;
}

三、高精度乘法

P1303 A*B Problem

题目背景

高精度乘法模板题。

题目描述

给出两个非负整数，求它们的乘积。

输入格式

输入共两行，每行一个非负整数。

输出格式

输出一个非负整数表示乘积。

输入输出样例 #1

输入 #1

1
2

输出 #1

2

说明/提示

每个非负整数不超过 $10^{2000}$。

解法

无进位相乘再相加：

• 还是「列竖式」，但是每一位相乘的时候不考虑进位，直接把乘的结果放在对应位上；
• 等到所有对应位置「乘完」并且「累加完」之后，「统一处理进位」。

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc;
// 高精度乘法的模板 c = a * b
void mul(int c[], int a[], int b[])
{
// 无进位相乘, 然后相加
for(int i = 0; i < la; ++i)
for(int j = 0; j < lb; ++j)
c[i + j] += a[i] * b[j];
// 处理进位
for(int i = 0; i < lc; ++i)
{
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
// 处理前导零
while(lc > 1 && c[lc – 1] == 0) lc—;
}
int main()
{
string s1, s2;
cin >> s1 >> s2;
la = s1.size(), lb = s2.size(), lc = la + lb;
for(int i = 0; i < la; ++i) a[i] = s1[la – i – 1] – '0';
for(int i = 0; i < lb; ++i) b[i] = s2[lb – i – 1] – '0';
mul(c, a, b);
for(int i = lc – 1; i >= 0; —i) cout << c[i];
return 0;
}

四、高精度除法

P1480 A/B Problem（高精度除法Ⅰ）

题目描述

输入两个整数 $a,b$，输出它们的商。

输入格式

两行，第一行是被除数，第二行是除数。

输出格式

一行，商的整数部分。

输入输出样例 #1

输入 #1

10
2

输出 #1

5

说明/提示

$0\le a\le 10^{5000}$，$1\le b\le 10^9$。

解法

模拟小学「列竖式」计算「两数相除」的过程（注意，我们这里是「高精度 ÷ 低精度」）。

定义一个指针 i 从「高位」遍历被除数，一个变量 t 标记当前「被除的数」，记除数是 b；

• 更新一个当前被除的数 t = t × 10 + a[i]；
• t/b 表示这一位的商，t%b 表示这一位的余数；
• 用 t 记录这一次的余数，遍历到下一位的时候重复上面的过程。

被除数遍历完毕之后，t 里面存的就是余数，但是商可能存在前导 0，注意清空。

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], b, c[N];
int la, lc;
// 高精度除法的模板 c = a / b (高精度 / 低精度)
void div(int c[], int a[], int b)
{
long long t = 0; // 标记每次除完之后的余数
for(int i = la – 1; i >= 0; —i)
{
// 计算当前的被除数
t = t * 10 + a[i];
c[i] = t / b;
t %= b;
}
// 处理前导零
while(lc > 1 && c[lc – 1] == 0) lc—;
}
int main()
{
string x;
cin >> x >> b;
la = x.size();
for(int i = 0; i < la; ++i) a[la – i – 1] = x[i] – '0';
lc = la;
div(c, a, b);
for(int i = lc – 1; i >= 0; —i) cout << c[i];
return 0;
}