C++ 高精度乘法

为什么要用高精度乘法？

上篇讲了高精度加法，但加法只能算加减。想算 12345678901234567890 × 9876543210？long long 直接溢出。

高精度乘法的思路：用字符串存数字，模拟竖式乘法。

思路拆解

模拟我们小学学的竖式乘法，分六步：

读入两个字符串（数字太大，必须当字符串读）
反转字符串（个位对齐索引 0）
字符转数字（'5' → 5）
逐位相乘，先不管进位（a[i] × b[j] 的结果加到 c[i+j]）
统一处理进位（满 10 进 1）
去掉前导零 → 反转 → 输出

乘法 vs 加法的关键区别

	加法	乘法
结果最大位数	`max(lenA, lenB) + 1`	`lenA + lenB`
核心运算	`c[i] = a[i] + b[i]`	`c[i+j] += a[i] × b[j]`
需要去前导零？	一般不需要	需要！乘 0 会得到一堆 0

逐行图解

以 12 × 34 为例：

反转后：a = "21", b = "43"
       a1 = [2, 1]
       a2 = [4, 3]

逐位相乘（先不管进位）：
  i=0, j=0: c[0] += 2×4 = 8
  i=0, j=1: c[1] += 2×3 = 6
  i=1, j=0: c[1] += 1×4 = 4  → c[1] = 10
  i=1, j=1: c[2] += 1×3 = 3

c = [8, 10, 3]

统一进位：
  c[0]=8  <10，不变
  c[1]=10 ≥10 → c[2]+=1, c[1]=0
  c[2]=4  <10，不变

c = [8, 0, 4]

反转回来：408 ✅  (12×34=408)

核心公式：c[i+j] += a[i] × b[j]

为什么是 i+j？因为第 i 位代表 10^i，第 j 位代表 10^j，它们的乘积代表 10^(i+j)，自然落到结果的第 i+j 位。

完整代码（带注释）

#include <bits/stdc++.h>
using namespace std;

string a, b;

int main() {
    getline(cin, a);
    getline(cin, b);

    // 1. 反转 —— 让个位对齐数组下标 0
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    // 2. 乘法结果最多 a.size() + b.size() 位
    int MaxLen = a.size() + b.size();

    vector<int> a1(MaxLen + 1, 0);  // 乘数 A 的每一位
    vector<int> a2(MaxLen + 1, 0);  // 乘数 B 的每一位
    vector<int> a3(MaxLen + 1, 0);  // 结果数组

    // 3. 字符转数字
    for (int i = 0; i < a.size(); i++) {
        a1[i] = a[i] - '0';
    }
    for (int i = 0; i < b.size(); i++) {
        a2[i] = b[i] - '0';
    }

    // 4. 逐位相乘，先不考虑进位
    //    核心：第 i 位 × 第 j 位 → 贡献到第 i+j 位
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            a3[i + j] += a1[i] * a2[j];
        }
    }

    // 5. 统一处理进位
    for (int i = 0; i <= MaxLen; i++) {
        if (a3[i] >= 10) {
            a3[i + 1] += a3[i] / 10;  // 进位加到下一位
            a3[i] %= 10;               // 当前位只保留个位
        }
    }

    // 6. 去掉前导零
    //    比如 123 × 0 = 000，需要变成 0
    int Len = a3.size();
    while (Len > 1 && a3[Len - 1] == 0) {
        Len--;
    }
    a3.resize(Len);

    // 7. 反转回来，输出
    reverse(a3.begin(), a3.end());
    for (int i = 0; i < Len; i++) {
        cout << a3[i];
    }

    return 0;
}

运行示例

输入：
12345678901234567890
9876543210

输出：
121932631137021795223746380112100

常见踩坑指南

🔴 坑 1：结果数组开太小

// ❌ 错误 —— 照搬加法的 MaxLen
int MaxLen = max(a.size(), b.size());  // 乘法不够用！

// ✅ 正确 —— 乘法结果最多 a.size() + b.size() 位
int MaxLen = a.size() + b.size();

99 × 99 = 9801，两个 2 位数相乘得到 4 位数。如果不留够空间，最高位的进位没地方放。

🔴 坑 2：忘记去前导零

// ❌ 没有这段代码，123 × 0 输出 "000"
// ✅ 必须去掉末尾的多余零
int Len = a3.size();
while (Len > 1 && a3[Len - 1] == 0) {
    Len--;
}
a3.resize(Len);

为什么 Len > 1？ 如果结果是 0，至少要保留一位 0。写成 Len > 0 会把唯一的 0 也删掉，什么都不输出。

🟡 坑 3：进位循环边界不对

// ❌ 错误 —— 只循环到 MaxLen-1
for (int i = 0; i < MaxLen; i++) { ... }

// ✅ 正确 —— 循环到 MaxLen（含）
for (int i = 0; i <= MaxLen; i++) { ... }

因为 a3[MaxLen-1] 的进位要写到 a3[MaxLen]，如果循环不包含 MaxLen，最高位的进位就丢了。

🟡 坑 4：混淆加法和乘法的进位时机

加法可以「边加边进位」：

for (int i = 0; i < MaxLen; i++) {
    a3[i] += a1[i] + a2[i];
    if (a3[i] >= 10) { a3[i+1]++; a3[i] -= 10; }
}

乘法不能边乘边进位！因为同一个 c[i+j] 可能被多对 (i, j) 累加，中途进位会打乱后续累加。正确做法是先全部乘完，再统一进位。

总结

高精度乘法的核心就三句话：

反转 → 逐位相乘累加到 c[i+j] → 统一进位 → 去前导零 → 反转回来

和加法的最大区别：结果长度是两数长度之和，以及必须去掉前导零。