c++中如何实现大数乘法_c++分治思想或模拟乘法算法【实例】_技术教程

不能直接用 long long 做大数乘法，因其最大仅约 1.8×10¹⁹，百位以上字符串相乘必溢出；需手写模拟竖式（主流）或 Karatsuba（千位以上才优）。

为什么不能直接用 `long long` 做大数乘法

因为 C++ 原生整型有上限：long long 最大只能表示约 1.8×10¹⁹，两个 10 位数相乘就可能溢出。一旦输入是几百位的字符串数字（比如 RSA 密钥运算、高精度财务计算），必须自己实现乘法逻辑。

两种主流思路：一是模拟手算竖式（直观、易调试），二是分治（如 Karatsuba，理论更快但常数大，百位内反而更慢）。实际工程中，99% 场景用模拟法就够了。

模拟竖式乘法：核心是「按位乘 + 错位累加」

把两个字符串 a 和 b 当作数字，从右往左遍历每一位，a[i] * b[j] 的结果应加到结果数组的 i + j + 1 位置（下标从 0 开始，低位在右），再统一处理进位。

结果最多有 a.size() + b.size() 位
，初始化为全 0 的 vector
a[i] 对应十进制位权是 10^(a.size()-1-i)，所以 a[i] × b[j] 贡献到结果的第 (a.size()-1-i) + (b.size()-1-j) = a.size()+b.size()-2-i-j 位 → 换成从左到右下标就是 i + j + 1
最后要去掉前导零，但至少保留一位（比如 "0" × "0" 得 "0"）

string multiply(string a, string b) {
    if (a == "0" || b == "0") return "0";
    vector res(a.size() + b.size(), 0);
    for (int i = a.size() - 1; i >= 0; i--) {
        for (int j = b.size() - 1; j >= 0; j--) {
            int mul = (a[i] - '0') * (b[j] - '0');
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + res[p2];
            res[p2] = sum % 10;
            res[p1] += sum / 10;
        }
    }
    string ans;
    bool leading = true;
    for (int d : res) {
        if (leading && d == 0) continue;
        leading = false;
        ans += ('0' + d);
    }
    return ans.empty() ? "0" : ans;
}

Karatsuba 分治乘法：只在千位以上才值得考虑

Karatsuba 把两个 n 位数拆成高位/低位两部分：x = x1 * 10^m + x0，y = y1 * 10^m + y0，然后用 3 次递归乘法代替常规的 4 次：xy = x1y1 * 10^(2m) + ((x1+x0)(y1+y0) - x1y1 - x0y0) * 10^m + x0y0。

但要注意：