P1303 A*B Problem

题目背景

高精度乘法模板题。

题目描述

给出两个非负整数，求它们的乘积。

输入格式

输入共两行，每行一个非负整数。

输出格式

输出一个非负整数表示乘积。

输入输出样例 #1

输入 #1

1 
2

输出 #1

2

说明/提示

每个非负整数不超过 \(10^{2000}\)。

Tip

B站讲解

📌 题目分析

给定数据：

A, B ≤ 10^2000

求两个超大非负整数的乘积。

👉 本质：

高精度运算 / 模拟乘法竖式

👉 类型：

高精度乘法模板

🧠 解题思路

1️⃣ 为什么需要高精度乘法

数据范围极其夸张：

最大达到 2000 位数字

远远超出了 C++ 中 long long 的极限（约 19 位数字），必须使用字符串（string）读取，并借助数组（vector 或 int 数组）来模拟数学运算。

2️⃣ 核心逻辑（竖式乘法原理）

回顾小学学过的多位数乘法：我们用第二个数字的每一位去乘第一个数字的每一位，然后错位相加。 如果在程序中将两个字符串倒序（让下标 0 代表个位，下标 1 代表十位），会发现一个极其优美的规律：

A 的第 i 位 乘以 B 的第 j 位
其结果必定累加到 答案的第 (i + j) 位上

公式：

res[i + j] += A[i] * B[j]

3️⃣ 处理进位与数组长度

两个长度分别为 \(N\) 和 \(M\) 的数字相乘，其结果的长度最大不会超过：

N + M

所以我们可以直接开一个大小为 \(N+M\) 的数组。先不考虑进位，通过两层循环把所有的乘积累加到对应的 res[i+j] 中，最后再统一遍历一次数组，处理所有位置的逢十进一。

4️⃣ 时间复杂度

两层嵌套循环，遍历两个字符串的长度：

O(N × M)

最大 \(2000 \times 2000 = 4 \times 10^6\) 次计算，在 C++ 中只需几毫秒即可跑完，完全在 1 秒的时限内。

---

💻 C++代码

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

int main() {
    // 优化输入输出流速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b;
    cin >> a >> b;

    // 特判：如果有一个数为 0，直接输出 0
    if (a == "0" || b == "0") {
        cout << 0 << "\n";
        return 0;
    }

    // 1. 字符串反转，让下标 0 成为个位
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int lenA = a.length();
    int lenB = b.length();
    // 结果的最大长度为 lenA + lenB
    vector<int> res(lenA + lenB, 0);

    // 2. 模拟竖式乘法（先不处理进位，全部累加）
    for (int i = 0; i < lenA; i++) {
        for (int j = 0; j < lenB; j++) {
            res[i + j] += (a[i] - '0') * (b[j] - '0');
        }
    }

    // 3. 统一处理进位
    int carry = 0;
    for (int i = 0; i < res.size(); i++) {
        res[i] += carry;
        carry = res[i] / 10;
        res[i] %= 10;
    }

    // 4. 去除前导零（比如 99 * 0 这种未特判的情况，或者最高位没进位留下的 0）
    int len = res.size() - 1;
    while (len > 0 && res[len] == 0) {
        len--;
    }

    // 5. 倒序输出结果
    string ans = "";
    for (int i = len; i >= 0; i--) {
        ans += to_string(res[i]);
    }

    cout << ans << "\n";

    return 0;
}

---

⚠️ 易错点

❌ 1. 数组索引的累加使用的是 +=

很多初学者会写成：

res[i + j] = (a[i] - '0') * (b[j] - '0'); // 错误

错位相加时，同一个位置（如十位）是由多个乘积组合而成的，必须使用 += 来累加。

❌ 2. 忘记处理乘数为 0 的特判

如果输入是 12345 和 0。 如果不写 if (a == "0" || b == "0")，且最后也没有正确的去前导零逻辑，程序很容易输出一堆 00000。遇到乘法，永远优先考虑 0 的情况。

❌ 3. 数组大小开错

加法的最大长度是 \(\max(A, B) + 1\)。 乘法的最大长度是 \(A\text{的长度} + B\text{的长度}\)。 千万不要混淆。

---

🚀 一句话总结

高精度乘法 = 倒序错位相乘累加 (res[i+j] += A[i]*B[j]) + 统一处理进位 + 去除前导零

---

🔥 补充

当数据范围进一步扩大（比如达到 \(10^5\) 或 \(10^6\) 级别时）：

• \(O(N^2)\) 的时间复杂度会超时（TLE）。
• 此时需要使用更高级的数学算法，例如 FFT（快速傅里叶变换），可以将时间复杂度降至 \(O(N \log N)\)。
• 但对于本题 \(2000\) 的范围，朴素的 \(O(N^2)\) 竖式模拟是最稳妥且代码最易读的选择。