高精度乘法

基本原理

高精度乘高精度，仍然模拟手工竖式乘法的过程。例如计算 123 × 45：

      1 2 3
×       4 5
-----------
      6 1 5   (123 × 5)
+   4 9 2     (123 × 4，向左偏移一位)
-----------
    5 5 3 5

在计算机中，我们使用数组（小端序）存储每一位，然后：

1. 用一个双重循环，将第一个数的每一位乘以第二个数的每一位。
2. 乘积的个位放在结果数组的对应位置（下标 i+j），十位及以上作为进位累加到更高位。
3. 最后处理所有进位，并去除前导零。

算法步骤

1. 初始化结果数组 c，长度至少为 len(a)+len(b)，所有元素为 0。
2. 遍历 i 从 0 到 len(a)-1：
   • 初始化进位 carry = 0。
   • 遍历 j 从 0 到 len(b)-1：
     • temp = c[i+j] + a[i] * b[j] + carry
     • c[i+j] = temp % 10
     • carry = temp / 10
   • 如果 carry > 0，继续向高位传递：c[i+len(b)] += carry，但这里需要循环处理进位（因为一次进位可能传播多位）。简便做法是在内层循环结束后，用 while 处理剩余进位。
3. 去除结果数组末尾（高位）的多余零，但至少保留一位（结果为 0 时保留一个 0）。

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 字符串转小端序 vector
vector<int> strToVec(const string& s) {
    vector<int> v;
    for (int i = s.size() - 1; i >= 0; --i)
        v.push_back(s[i] - '0');
    return v;
}

// 去除前导零
void trim(vector<int>& v) {
    while (v.size() > 1 && v.back() == 0)
        v.pop_back();
}

// 高精度 × 高精度
vector<int> mulBig(const vector<int>& a, const vector<int>& b) {
    vector<int> c(a.size() + b.size(), 0); // 结果最多有 len(a)+len(b) 位
    for (size_t i = 0; i < a.size(); ++i) {
        int carry = 0;
        for (size_t j = 0; j < b.size(); ++j) {
            int temp = c[i + j] + a[i] * b[j] + carry;
            c[i + j] = temp % 10;
            carry = temp / 10;
        }
        // 处理剩余进位
        size_t idx = i + b.size();
        while (carry) {
            int temp = c[idx] + carry;
            c[idx] = temp % 10;
            carry = temp / 10;
            ++idx;
        }
    }
    trim(c);
    return c;
}

// 输出大数
void printVec(const vector<int>& v) {
    for (int i = v.size() - 1; i >= 0; --i)
        cout << v[i];
    cout << endl;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> a = strToVec(s1);
    vector<int> b = strToVec(s2);
    vector<int> result = mulBig(a, b);
    printVec(result);
    return 0;
}