题解 | #大整数相乘# 模拟竖式

#include <iostream>
using namespace std;

int main() {
    string str1, str2;
    while (cin >> str1 >> str2) {
        long len1 = str1.size();
        long len2 = str2.size();
        long len = len1 + len2;
        string ans(len, '0');
        int carry = 0; // 进位
        int shift = 0; // 移位
        int i = 0, j = 0; // i遍历str1，j遍历str2
        int num1 = 0, num2 = 0; // num1，num2分别表示str1，str2当前位置上的数，
        int ansCurr = 0, mulCurr; // 分别表示 答案当前位置上的数 和 当前位置相乘的结果
        for (i = 0; i < len2; i++) {
            carry = 0; // 进位重置
            num2 = str2[len2 - i - 1] - '0'; // 取出str2当前位置的数
            for (j = 0; j < len1; j++) { // 对于str1的每一位
                num1 = str1[len1 - j - 1] - '0';  // 取出str1当前位置的数
                ansCurr = ans[len - shift - j - 1] - '0'; // 取出ans当前位置的数
                mulCurr = num1 * num2 + ansCurr + carry; // 当前位置的相乘结果
                carry = mulCurr / 10; // 计算进位
                ans[len - shift - j - 1] = mulCurr % 10 + '0'; // 当前位置应填入的数
            }
            // 如果还有进位，直接填入对应位置
            if (carry != 0) {
                ans[len - shift - j - 1] = carry + '0';
            }
            // 移位加1，进入下一轮
            shift++;
        }
        // 抹除前0
        if (ans[0] == '0') {
            ans.erase(0, 1);
        }
        cout << ans << endl;
    }
    return 0;
}

时间复杂度：O(len1*len2)，用于遍历并计算两数相乘

空间复杂度：O(len1+len2)，用于存储结果