高精度乘法（高×高）

高精度乘法（高×高）

前言

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

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

A*B Problem P1303

题目描述

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

提示

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

讲解

模拟乘法：

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

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

#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;
}