经典算法题：大数乘法之乘法累加算法 Karatsuba算法（远远超出long long范围）

问题：

超过100位数字的整数的乘法，无法直接调用*运算；

例如：

求 1234567891011121314151617181920 * 2019181716151413121110987654321 的乘积结果

需要转化成数组问题或者字符串问题求解，答案也用数组表示；

思路有两种：

• 乘法累加法：

        输入数组num1 num2，注意要颠倒顺序 因为要从低位往高位处理（当然也可以不处理）；

        第i位数字与第j位数字相乘的结果 应保存到arr(i+j)位；

        然后对arr数组进位c进行处理；

        输出答案字符串res（删除前导0）。

算法复杂度 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    string num1, num2;
    cin >> num1 >> num2;
    if(num1.size() == 0 || num2.size() == 0)
    {
        cout << 0 << endl;
        return 0;
    }
    reverse(num1.begin(),num1.end());
    reverse(num2.begin(),num2.end());
    vector<int> arr(num1.size() + num2.size());
    for(int i = 0; i < num1.size(); i++)
    {
        for(int j = 0; j < num2.size(); j++)
        {
            arr[i+j] += (num1[i] - '0') * (num2[j] - '0');
        }
    }
    string res;
    int c = 0;
    for(int i = 0; i < arr.size(); i++)
    {
        int num = arr[i] + c;
        c = num/10;
        res = char(num%10 + '0') + res;
    }
    if(c > 0)
        res = to_string(c)+res;
    int i = 0;
    while(i < res.size() && res[i] == '0')
        i++;
    cout << res.substr(i) << endl;
}

• Karatsuba算法 分治法

       例如： A  |  B  *  C  |  D

        其中数字1（A|B）和数字2（C|D）的分段一致(n/2)；

        处理如下：

       而

        这样的话就可以利用前后得到的结果；

        大问题可以依次分解成为小问题，分治法的思路！

        算法复杂度：

        注意：显示的数字顺序与实际相反，因此最后的结果需要反转！

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//所有数字都是从低到高 比如string "123" 表示数字321
string add(string a, string b)
{
    int m = a.size(), n = b.size();
    if(m == 0) return b;
    if(n == 0) return a;
    int i = 0, j = 0, c = 0;
    string res;
    while(i < m && j < n)
    {
        int num = a[i] - '0' + b[j] - '0' + c;
        c = num/10;
        res += (char)(num%10 + '0');
        i++;
        j++;
    }
    while(i < m)
    {
        int num = a[i] - '0' + c;
        c = num/10;
        res += (char)(num%10 + '0');
        i++;
    }
    while(j < n)
    {
        int num = b[j] - '0' + c;
        c = num/10;
        res += (char)(num%10 + '0');
        j++;
    }
    if(c > 0)
        res += '1';
    return res;
}
//不考虑出现负数可能出现的情况
string sub(string a, string b)
{
    int m = a.size(), n = b.size();
    if(m == 0 || n == 0) return "0";
    int i = 0, j = 0, c = 0;
    string res;
    while(i < m && j < n)
    {
        int num = (a[i] - '0') - (b[j] - '0') - c;
        if(num < 0)
        {
            c = 1;
            num += 10;
        }
        else c = 0;
        res += (char)(num%10 + '0');
        i++;
        j++;
    }
    while(i < m)
    {
        int num = a[i] - '0' - c;
        if(num < 0)
        {
            c = 1;
            num += 10;
        }
        else c = 0;
        res += (char)(num%10 + '0');
        i++;
    }
    while(j < n)
    {
        int num = - b[j] + '0' - c;
        if(num < 0)
        {
            c = 1;
            num += 10;
        }
        else c = 0;
        res += (char)(num%10 + '0');
        j++;
    }
    //cout << "res = " << res << endl;
    int k = res.size() -1;
    while(k >= 0  && res[k] == '0')
        k--;
    return res.substr(0,k+1);
}
string mul(string a, string b)
{
    int m = a.size(), n = b.size();
    string res;
    if(m == 0 && n == 0) return "0";
    else if(m == 1 && n == 1)
    {
        int num = (a[0]-'0')*(b[0]-'0');
        res = to_string(num);
        reverse(res.begin(),res.end());
        return res;
    }
    int len = max(m,n);
    while(m < len)
    {
        a.push_back('0');
        m++;
    }
    while(n < len)
    {
        b.push_back('0');
        n++;
    }
    int mid = len/2;
    if(len%2 == 1)
        mid += 1;
    string A = a.substr(mid), B = a.substr(0,mid);
    string C = b.substr(mid), D = b.substr(0,mid);
    string AC = mul(A,C);
    cout << A << " * " << C << " = " << AC << endl;
    string BD = mul(B,D);
    cout << B << " * " << D << " = " << BD << endl;
    string M0 = add(A,B);//A+B
    cout << A << " + " << B << " = " << M0 << endl;
    string M1 = add(C,D);//C+D
    cout << C << " + " << D << " = " << M1 << endl;
    string M2 = mul(M0,M1);
    cout << M0 << " * " << M1 << " = " << M2 << endl;
    string M3 = sub(M2,AC);
    cout << M2 << " - " << AC << " = " << M3 << endl;
    M3 = sub(M3,BD);
    cout << "M3" << " - " << BD << " = " << M3 << endl;
    if(BD.size() > mid)
    {
        M3 = add(M3,BD.substr(mid));
        BD = BD.substr(0,mid);
    }
    if(M3.size() > mid)
    {
        AC = add(AC,M3.substr(mid));
        M3 = M3.substr(0,mid);
    }
    res = BD+M3+AC;
    return res;
}
int main()
{
    string num1, num2;
    cin >> num1 >> num2;
    if(num1.size() == 0 || num2.size() == 0)
    {
        cout << 0 << endl;
        return 0;
    }
    reverse(num1.begin(),num1.end());
    reverse(num2.begin(),num2.end());
    string res = mul(num1,num2);
    reverse(res.begin(),res.end());
    int i = 0;
    while(i < res.size() && res[i] == '0')
        i++;
    cout << res.substr(i) << endl;
}

• 答案揭晓

1234567891011121314151617181920 * 2019181716151413121110987654321 =

2492816912877266687794240983772975935013386905490061131076320

请验证一下。