高精度乘法——多位数乘多位数的拆解游戏

高精度乘法——像手算竖式一样拆解大数相乘

在编程中，我们常常遇到两个非常大的整数相乘，比如两个都是几百位甚至上千位的数。普通 int 或 long long 根本装不下。这时就需要高精度乘法——用数组或向量来模拟手算竖式的过程，把乘法拆成一个个小步骤，最后累加得到结果。

高精度乘法的思路完全来自我们小学学过的多位数乘法竖式。例如计算 123 × 45：

   1 2 3
×    4 5
---------
   6 1 5   ← 个位5乘123
+ 4 9 2    ← 十位4乘123，注意向左错一位（相当于乘10）
---------
   5 5 3 5

在 C++ 里，我们用两个 vector<int> 来存储大数的每一位（低位在前，即个位在索引0），然后模仿这个竖式过程，把每一位的乘积加到对应位置上，最后统一处理进位。

1. 竖式计算的秘密：拆成多个一位乘法再相加

手算竖式：从乘数的个位开始，依次乘以被乘数的每一位，得到一行中间结果，然后根据位权向左错位，最后把所有的中间结果相加。
编程实现：用两层循环，外层遍历乘数的每一位（从个位开始），内层遍历被乘数的每一位。乘数第 i 位（从0开始）与被乘数第 j 位相乘的结果，应该加到结果数组的第 i+j 位上（因为位权是 10^(i+j)）。

生活中的例子：小明每天有 123 元零花钱，连续 45 天，他一共得到多少钱？就是 123 × 45。我们先把45拆成 5 + 40，先算 123 × 5 = 615，再算 123 × 40 = 4920，最后加起来就是 5535 元。程序里也是这个思路，只不过把“5”和“40”拆得更细：每一位数字单独乘，再根据位权放到正确位置。

2. 用数组来模拟竖式：数字存储与低位优先

将数字字符串逆序存入 vector：比如 "123" 存入 a 得到 [3, 2, 1]（个位在前）。
为什么低位在前？因为这样数组索引 i 正好代表 10^i 的位权，方便计算 i+j 的偏移量。
结果数组的大小至少为 a.size() + b.size()，因为乘积最大位数不会超过两数位数之和（例如两位×三位最多五位）。

代码准备：

string s1 = "123", s2 = "45";
vector<int> a, b;
// 从字符串末尾开始，把每个字符转成整数，存入vector
for (int i = s1.size() - 1; i >= 0; i--) a.push_back(s1[i] - '0');
for (int i = s2.size() - 1; i >= 0; i--) b.push_back(s2[i] - '0');
// 现在 a = [3,2,1]  b = [5,4]

3. 核心算法：两层循环累加乘积

先创建一个结果数组 c，长度 a.size() + b.size()，全部初始化为0。
两层循环：for (int i = 0; i < a.size(); i++) 遍历被乘数每一位，for (int j = 0; j < b.size(); j++) 遍历乘数每一位。
核心语句：c[i + j] += a[i] * b[j]; 这里只做简单累加，先不处理进位，因为后面统一进位更高效。

举例说明：

a[0]=3, a[1]=2, a[2]=1（代表123）
b[0]=5, b[1]=4（代表45）
循环计算：
- i=0,j=0: c[0] += 3*5 =15
- i=0,j=1: c[1] += 3*4 =12
- i=1,j=0: c[1] += 2*5 =10 → 此时 c[1]=12+10=22
- i=1,j=1: c[2] += 2*4 =8
- i=2,j=0: c[2] += 1*5 =5 → 此时 c[2]=8+5=13
- i=2,j=1: c[3] += 1*4 =4
得到中间结果 c = [15, 22, 13, 4, 0]

4. 处理进位：把超过10的位数向前“进”

遍历 c 的每一位，用一个变量 carry 记录进位数。
对于第 i 位，当前值加上进位：int tmp = c[i] + carry;
保留个位：c[i] = tmp % 10;
新进位：carry = tmp / 10;
循环结束后，如果 carry 不为0，需要继续添加到数组末尾（但一般情况下循环已经包含了最高位，因为数组长度足够；如果最高位还有进位，则需要 while (carry) { c.push_back(carry % 10); carry /= 10; }——但我们的数组大小已经设为 a+b，所以这里不必额外处理，因为进位后的最高位最多是 a+b 位；不过为了安全，可以在循环后处理一下残留进位，但本例中循环次数已覆盖所有可能的进位位置，所以通常不需要）。

示例：上面 c = [15, 22, 13, 4, 0]

i=0: tmp=15+0=15, c[0]=5, carry=1
i=1: tmp=22+1=23, c[1]=3, carry=2
i=2: tmp=13+2=15, c[2]=5, carry=1
i=3: tmp=4+1=5, c[3]=5, carry=0
i=4: tmp=0+0=0, c[4]=0, carry=0 结果 c = [5,3,5,5,0]（翻转后是55350？不对，实际应该是5535，要记得去掉前导零）。

5. 去掉前导零，得到最终结果

高位的0（即 c.back()，因为数组低位在前，高位在后）代表没有数字，比如上面的 c[4]=0 就是多余的高位0。
用 while (c.size() > 1 && c.back() == 0) c.pop_back(); 去掉末尾的0，保留至少一位（防止结果为0时全部被删光）。

最终 c = [5,3,5,5]，逆序输出得到 5535。

常见错误与注意事项

数组大小不够：结果数组长度应该是 a.size() + b.size()，不要写成 max(a.size(), b.size()) 或两者之和减1，否则可能出现越界或丢失最高位进位。
忘记处理进位：如果两数乘积导致某一位超过100甚至更大，必须逐位进位，不能只考虑一次进位。
去掉前导零过度：当结果为0时（如 0 * 12345），如果去掉所有前导零，数组会变空，导致输出错误。所以要保留至少一位：while (c.size() > 1 && c.back() == 0)。
输入输出顺序：读入字符串后要逆序存入数组，输出时也要逆序。
注意数据类型：a[i] * b[j] 是两个 int 相乘，结果可能超过 int 范围（但最大单个数字9*9=81，不会超，但累加后可能超过，不过我们处理进位时临时变量用了 int，这不会有问题，因为每一位最大可能值：假设两个1000位的数，对应位乘积之和最多 9*9*1000=81000，加上进位也不超过 int 范围）。如果位数非常大（几万位），建议用 long long 暂存。

完整可运行代码（带详细中文注释）

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 高精度乘法，接收两个逆序存储的 vector，返回逆序的结果
vector<int> mul(vector<int> &a, vector<int> &b) {
    int len_a = a.size();          // 被乘数的位数
    int len_b = b.size();          // 乘数的位数
    vector<int> c(len_a + len_b, 0); // 结果数组，长度=两数位数之和，初始全0

    // 两层循环：乘数每一位乘以被乘数每一位
    for (int i = 0; i < len_a; i++) {
        for (int j = 0; j < len_b; j++) {
            c[i + j] += a[i] * b[j]; // 乘积加到对应位置，暂不进位
        }
    }

    // 统一处理进位
    int carry = 0;                  // 保存进位值
    for (int i = 0; i < c.size(); i++) {
        int temp = c[i] + carry;   // 当前位加上进位
        c[i] = temp % 10;          // 保留个位
        carry = temp / 10;         // 新的进位
    }
    // 如果最后还有进位，需要追加（但我们的数组长度已足够，一般不会执行）
    while (carry > 0) {
        c.push_back(carry % 10);
        carry /= 10;
    }

    // 去掉前导零（高位多余的0），但保留至少一位
    while (c.size() > 1 && c.back() == 0) {
        c.pop_back();
    }
    return c;
}

int main() {
    string s1, s2;
    cout << "请输入两个大整数（可带前导零）：" << endl;
    cin >> s1 >> s2;

    // 将字符串逆序存入 vector，低位在前
    vector<int> a, b;
    for (int i = s1.size() - 1; i >= 0; i--) {
        a.push_back(s1[i] - '0');  // 字符转数字
    }
    for (int i = s2.size() - 1; i >= 0; i--) {
        b.push_back(s2[i] - '0');
    }

    vector<int> c = mul(a, b);    // 调用乘法函数

    // 逆序输出结果（高位在前）
    cout << "结果 = ";
    for (int i = c.size() - 1; i >= 0; i--) {
        cout << c[i];
    }
    cout << endl;

    return 0;
}

运行示例：

请输入两个大整数（可带前导零）：
123 45
结果 = 5535

另一个测试：999 999 结果应为 998001。