高精度乘法（高×高）

前言

ACWing算法基础课讲解了高×低的乘法，这里高×高作为一个进一步的补充，也是对闫总的板子做一个补充。

以下内容改编自《洛谷深入浅出》123页，我对代码进行了一点修改。

A*B Problem P1303

题目描述

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

提示

每个非负整数的位数不超过2000。

讲解

模拟乘法：

数 第6位 第5位 第4位 第3位 第2位 第1位
a 5 1 4
b 4 9 5
a*b [1] 25 5 20
a*b [2] 45 9 36
a*b [3] 20 4 16
中间产物 20 49 50 41 20
处理进位 2 5 4 4 3 0
结果 2 5 4 4 3 0

仔细观察，可以发现 a[i]*b[j] 的贡献全部在中间产物的第 i+j-1 位上。这个性质提供了一个简便的写法：可以把所有贡献算出来，最后一口气处理所有进位问题。这样可以避免处理多次进位事件，优化效率——计算机中取模的效率远低于加法和乘法。

这个进位模拟过程与加法过程大同小异，都是把个位数留下，把个位以外的数字贡献给下一位，具体可见如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1e5;
const int M = 1e8;

LL A[N]={0}, B[N]={0}, C[M]={0}; // 下标从1开始 
LL lena, lenb, len;

void mul() {	
	for (LL i = 1; i <= lena; i++)
		for (LL j = 1; j <= lenb; j++)
			C[i + j - 1] += A[i] * B[j]; // 计算贡献 
	for (LL i = 1; i <= len; i++) { // 进位 
		C[i + 1] += C[i] / 10;
		C[i] %= 10;
	}
	while (len > 1 && !C[len]) len--; // 去掉前导零
}

int main() {
	string a, b;
	cin >> a >> b;
	lena = a.size();
	lenb = b.size();
	len = lena + lenb; // 乘积的位数不超过两数的位数之和
	for (LL i = 1; i <= lena; i++) A[i] = a[lena - i] - '0';
	for (LL i = 1; i <= lenb; i++) B[i] = b[lenb - i] - '0';
	mul(); 
	for (LL i = len; i >= 1; i--) printf("%d", C[i]);
	
	return 0;
}