2. 大整数乘法

问题描述

求两个不超过200位的非负整数的积。

输入形式

有两行，每行是一个不超过200位的非负整数，没有多余的前导0。

输出形式

一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。

样例输入

1234567890

9876543210

样例输出

12193263111263526900

思路：设两个整数X和Y相乘，先看X，Y位数一致时的情况，

将四次乘法变成了三次乘法，时间复杂度为T(n)=3T(n/2)+O(n) (n > 1)，根据Master定理 。当X,Y位数不一致时，就为位数小的那方补零使其对齐。

在两数位数差距较大时还可以继续优化。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<ctime>

using namespace std;

bool compare(string a, string b, int alen, int blen){
    if (alen > blen) return true;
    if (alen < blen) return false;
    if (a >= b) return true;
    else return false;
}

void fun(string &a, string &b, string &c, string &d){
    int k = 0;
    while(a[k] == '0' && k < a.length()-1)
        a.erase(a.begin() + k);
    k = 0;
    while(b[k] == '0' && k < b.length()-1)
        b.erase(b.begin() + k);
    k = 0;
    while(c[k] == '0' && k < c.length()-1)
        c.erase(c.begin() + k);
    k = 0;
    while(d[k] == '0' && k < d.length()-1)
        d.erase(d.begin() + k);
}

string subtract(string a, string b){
    int alen = a.length();
    int blen = b.length();
    bool judge = compare(a, b, alen, blen);
    if (!judge) {
        swap(a, b);
        swap(alen, blen);
    }
        
    string result;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    //cout << a << ' ' << b << endl; 
    for (int i = 0; i < blen; i++) {
        int res;
        if ((a[i] - '0') - (b[i] - '0') < 0) {
            res = (a[i] - '0') + 10 - (b[i] - '0');
            int j = i + 1;
            while(a[j] == '0' && j < alen) {
                a[j] = '9'; 
                j++;
            }    
            a[j] -= 1;
        }
        else res = (a[i] - '0') - (b[i] - '0');
        result += res + '0';    
    }
    result += a.substr(blen, alen - 1);
    if (!judge) result += '-'; 
    reverse(result.begin(), result.end());
    return result;
}

string add(string a, string b){
    
    int adv = 1;
    if (a[0] == '-' && b[0] != '-') {
        a.erase(a.begin());
        return subtract(b, a);
    }
    if (a[0] != '-' && b[0] == '-') {
        b.erase(b.begin());
        return subtract(a, b);
    }
    if (a[0] == '-' && b[0] == '-') {
        adv = -1;
        a.erase(a.begin());
        b.erase(b.begin());
    }
    int alen = a.length();
    int blen = b.length();
    if (alen < blen) {
        swap(a,b);
        swap(alen, blen);
    }
    
    string s(alen-blen, '0');
    b = s + b;
    //cout << a << ' ' << b << endl;
    int flag = 0;
    string result;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    for (int i = 0; i < alen; i++) {
        int res = (a[i] - '0') + (b[i] - '0') + flag;
        result += '0' + (res % 10);
         if (res >= 10) flag = 1;
         else flag = 0;
    }
    if (flag == 1) result += '1';
    //result += a.substr(blen, alen - 1);
    if (adv == -1) result += '-';
    reverse(result.begin(), result.end());
    return result;
}

string multiply(string a, string b){
    int flag = 1;
    if(a[0] == '-') {
        a.erase(a.begin());
        flag = -flag;
    }
    if(b[0] == '-') {
        b.erase(b.begin());
        flag = -flag;
    }
    int alen = a.length();
    int blen = b.length();
    if (a[0] == '0' || b[0] == '0') return "0";
    if (alen < blen) {
        swap(a,b);
        swap(alen, blen);
    }
    string result;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int res = 0;
    for (int i = 0; i < blen; i++) {
        int adv = 0;
        string parameter;
        for (int j = 0; j < alen; j++) {
            res = (b[i] - '0') * (a[j] - '0') + adv;
            if (res >= 10) adv = res / 10;
            else adv = 0;
            parameter += (res % 10) + '0';
        }
        if (adv > 0) parameter += '0' + adv;
        reverse(parameter.begin(), parameter.end());
        //cout << parameter << endl;
        string s(i, '0');
        if (i == 0) result = parameter;
        else result = add(result, parameter+s);
        //cout << result << endl;
    }
    if (flag == -1) return "-"+result;
    return result;    
}

//10^n AC+10^(n/2){(A-B)(D-c)+AC+BD}+BD
//AC BD (A-B)(D-C)
string solve(string a, string b){
    int flag = 1;
    if(a[0] == '-') {
        a.erase(a.begin());
        flag = -flag;
    }
    if(b[0] == '-') {
        b.erase(b.begin());
        flag = -flag;
    }
    
    int alen = a.length();
    int blen = b.length();
    if (a[alen-1] =='0' && a[0] == '0' || b[blen-1] == '0' && b[0] == '0') return "0";
    if (alen < blen) {
        swap(a, b);
        swap(alen, blen);
    }     
    string s(alen - blen, '0');
    b = s + b;
    int n = alen;
    if(n == 1) {
        if (flag == -1) return '-' + multiply(a, b);
        else return multiply(a, b);    
    }
    int mid = n / 2;
    string A, B, C, D, AC, BD, X;
    A = a.substr(0, mid);
    B = a.substr(mid, n-mid);
    C = b.substr(0, mid);
    D = b.substr(mid, n-mid);
    
    fun(A, B, C, D);
    
    AC = solve(A, C);
    BD = solve(B, D);
    X = solve(subtract(A, B), subtract(D, C));
    //cout << A << ' ' << B << ' ' << C << ' ' << D << endl;
     //cout << AC << ' ' << BD << ' ' << X << endl;
    
    int x = n;
    int y = n / 2;
    if (n % 2) {
        x++; y++;
    }
    
    string s1(x, '0');
    string s2(y, '0');
    
    string result;
    if(flag==-1) result += '-';
    result += add(add(AC+s1, BD), add(X, add(AC, BD))+s2);
    //cout << add(AC+s1, BD) << ' ' << add(AC, BD) << ' ' << add(X, add(AC, BD)) <<' ' << add(X, add(AC, BD))+s2 << endl;
    return result;
}

int main(){
    string a, b, result;
    cin >> a >> b;
    result = multiply(a, b);
    cout << result;
    return 0;
}