练78.1 高精度乘法

解题思路

将两数数位倒序，每对数位a[i]、b[j]的乘积贡献到结果第i+j位。先累计全部乘积，再从低到高处理进位，去掉最高多余0。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

结果最多两数位数和那么长；不要使用内置整型保存整个数。

复杂度

分别A、B位，时间O(AB)，空间O(A+B)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b;
    cin >> a >> b;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    vector<int> c(a.size() + b.size() + 1);
    for (size_t i = 0; i < a.size(); i++)
        for (size_t j = 0; j < b.size(); j++)
            c[i + j] += (a[i] - '0') * (b[j] - '0');
    for (size_t i = 0; i + 1 < c.size(); i++) {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    for (int i = int(c.size()) - 1; i >= 0; i--)
        cout << c[i];
    cout << "\n";
    return 0;
}