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。

但要注意：

• 字符串需补前导零至等长且为 2 的幂次，否则递归边界难处理
• 每次递归都要做字符串加减和截取，小规模时开销远超收益
• 实测：当输入长度
• C++ 标准库无内置大数，若真要高性能，建议直接用 boost::multiprecision::cpp_int 或 OpenSSL 的 BIGNUM

容易被忽略的边界和性能陷阱

写完别急着交——这几个点一错就 WA 或 TLE：

• 输入含负号？题目没说就默认非负；若支持负数，先记符号，最后加 '-' 即可
• 空字符串或全是 '0' 的字符串（如 "000"）→ 必须预处理成 "0"
• 用 string 存中间结果时，反复 +=

  

  可能触发多次内存重分配；用 reserve() 预留空间能提速 10%–20%
• 不要在循环里调用 to_string() 或 stoi() —— 字符转数字一律用 c - '0'，避免异常和开销
• 如果后续还要做加减除，建议封装成类，统一管理数字存储格式（如逆序存 digits 更利于进位）

真正卡时间的不是算法本身，而是字符串操作的细节和内存访问模式。