分治法实现大整数乘法C++代码

分治法是一种常见的算法设计策略，常用于解决可以分解成规模更小的同类问题的问题。对于大整数乘法，可以将其转换为较小的整数乘法，并通过位运算简化。这里是一个简单的基于中国剩余定理（Chinese Remainder Theorem, CRT）的大整数乘法C++实现，通常这种方法称为Karatsuba算法的优化版本，如Toom-Cook算法。

#include <iostream>
#include <vector>

using namespace std;

// 辅助函数，计算两个较小的整数的乘积
long long multiply(int a, int b) {
    return (a * b) % 1000000007; // 使用模运算避免整数溢出
}

// 递归函数，实现分治大整数乘法
void karatsuba(long long x, long long y) {
    if (x < 10 && y < 10)
        return cout << multiply(x, y) << endl;
    
    int n = min({int(log2(abs(x))), int(log2(abs(y)))});
    long long a = x / pow(10, n), b = x % pow(10, n);
    long long c = y / pow(10, n), d = y % pow(10, n);

    long long z0 = karatsuba(a, d);
    long long z1 = karatsuba(b + c, pow(10, n) - 1); // 注意这个加法是带进位的
    long long z2 = karatsuba(b, c);

    // 根据中国剩余定理计算最终结果
    cout << ((z2 * pow(10, 2 * n)) % 1000000007 +
             ((z1 - z2 - z0) * pow(10, n)) % 1000000007 +
             z0) % 1000000007 << endl;
}

int main() {
    long long num1, num2;
    cin >> num1 >> num2;
    karatsuba(num1, num2);
    return 0;
}