高精度乘法（高×高）
前言
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 位上。这个性质提供了一个简便的写法：可以把所有贡献算出来，最后一口气处理所有进位问题。这样可以避免处理多次进位事件，优化效率——计算机中取模的效率远低于加法和乘法。
这个进位模拟过程与加法过程大同小异，都是把个位数留下，把个位以外的数字贡献给下一位，具体可见如下代码：
#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;
}
