大整数的乘法

std::vector<int> solve(std::string X, std::string Y) {
    std::vector<int> result(255, 0);
    std::function<void(std::string, std::string, int)> multiply = [&](std::string s, std::string t, int pos) {
        int n = (int) s.size(), m = (int) t.size();
        if (n == 0  m == 0) {                 // 位数为0时
            return ;
        } else if (n == 1 && m == 1) {          // 递归到当前数组s和t的位数全为1时
            result[pos] += (s[0] - '0') * (t[0] - '0');
            return ;
        } else {                                // 当数组s和t的位数至少有一个不为1时
            int n1 = n / 2;                     // n1为B的位数,B属于低位的那一部分
            int n2 = n - n1;                    // n2为A的位数,A属于高位的那一部分
            int m1 = m / 2;                     // m1为D的位数,D属于低位的那一部分
            int m2 = m - m1;                    // m2为D的位数,C属于高位的那一部分
            std::string A = s.substr(0, n2);    // 获取s的高位部分A
            std::string B = s.substr(n2);       // 获取s的低位部分B
            std::string C = t.substr(0, m2);    // 获取t的高位部分C
            std::string D = t.substr(m2);       // 获取t的低位部分D
            multiply(A, C, pos + n1 + m1);      // AC,在result[pos+n1+m1]的位置存储AC,也是说偏移pos+n1+m1位,pos初始化为0
            multiply(B, C, pos + m1);           // BC,偏移pos+m1位
            multiply(A, D, pos + n1);           // AD,偏移pos+1位
            multiply(B, D, pos);                // BD,偏移pos位
        }
    };
    multiply(X, Y, 0);

    int len = (int) X.size() + (int) Y.size();
    for (int i = 0; i <= len; i++) {
        int now = result[i] % 10;
        int bit1 = result[i] / 10 % 10;
        int bit2 = result[i] / 100;
        result[i] = now;
        result[i + 1] += bit1;
        result[i + 2] += bit2;
    }
    while (result.back() == 0) {
        result.pop_back();
    }

    return result;
}

最后更新: 2024年1月2日 21:37:12
创建日期: 2024年1月2日 19:47:42
回到页面顶部