解题思路

高精度乘法：两个不超过 240 位的大数相乘，结果最大约 480 位，必须用数组逐位处理。

思路：

1. 逆序存数组：把两个乘数逆序存进数组，个位在 a[0]、b[0]
2. 逐位相乘：模仿乘法竖式，a 的第 i 位乘 b 的第 j 位，结果加到结果的第 i+j 位
3. 处理进位：从低位到高位，某一位超过 10 就向高位进位
4. 去前导 0：从高位找第一个非 0 的位置，从这里开始输出

为什么乘到第 i+j 位？ 乘法竖式里，a 的个位（第0位）乘 b 的十位（第1位），结果放在第 0+1=1 位；a 的十位乘 b 的十位放在第 2 位。所以 a[i]×b[j] 加到 c[i+j]。

举例：111...111 × 222...222

• 每位 1×2=2，但逐位相乘后还要进位
• 结果是 24691358...（交错进位得到的）

参考代码

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

int a[250], b[250], c[505];

int main() {
    string s1, s2;
    cin >> s1 >> s2;

    int la = s1.size(), lb = s2.size();
    for (int i = 0; i < la; i++) a[la - 1 - i] = s1[i] - '0';
    for (int i = 0; i < lb; i++) b[lb - 1 - i] = s2[i] - '0';

    // 逐位相乘
    for (int i = 0; i < la; i++) {
        for (int j = 0; j < lb; j++) {
            c[i + j] += a[i] * b[j];
        }
    }

    // 处理进位
    for (int i = 0; i < la + lb; i++) {
        if (c[i] >= 10) {
            c[i + 1] += c[i] / 10;
            c[i] = c[i] % 10;
        }
    }

    // 去掉前导 0
    int p = la + lb;
    while (p > 0 && c[p] == 0) p--;

    for (int i = p; i >= 0; i--) cout << c[i];
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，双重循环逐位相乘
• 空间复杂度：O(N)，存结果的数组