大数乘法的深入讨论二（分治）

《大数乘法的深入讨论一》中介绍了最基本的模拟手工算法，它的时间复杂度为O(n²)，接下来将介绍一种更高效的算法——分治算法。

（原理&思路写得不太好，留个坑，以后有空了再改，但是代码一定是可以用的，亲自调过的）

算法的理论：

该算法的来源——高斯技巧（Gauss Trick）：
两个复数的乘法 涉及到4个乘法：

通过下式，可以将4个乘法化简到三个：

应用到大数乘法中：
将n位二进制整数X和Y都分为2段，每段的长为n/2

由此得到:

由主定理求得

算法的实现：

#include<bits/stdc++.h>
using namespace std;
string big_multiply(string a,string b,int n1,int n2);
int main(){
    string a,b;
    cout<<"输入待乘数：\n";
    while(cin>>a>>b){
        int n1 = a.length();
        int n2 = b.length();
        cout<<big_multiply(a,b,n1,n2)<<endl<<"\n输入待乘数：\n";
    }
    return 0;
}
string one_mul_n(string a,string b){  //1位*n位 
    vector<int> res(b.length()+2);
    string s_res;
    reverse(b.begin(),b.end());
    for(int i=0;i<b.length();i++){
        res[i]+=(a[0]-'0')*(b[i]-'0');
    }
    for(int i=0;i<res.size();i++){
        if(res[i]>9){
            res[i+1]+=res[i]/10;
            res[i]=res[i]%10;
        }
    }
    int index=res.size()-1;
    while(res[index]==0) index--;//找到非0的最高位
    for(int i=index;i>=0;i--){s_res+=res[i]+'0';} 
    return s_res;
}
string add(string a,string b,string c,string d){ //求和
    string s_res;
    int len1 = a.length()-1;
    int len2 = b.length()-1;
    int len3 = c.length()-1;
    int len4 = d.length()-1;
    int num = 0;
    int carry = 0;
    while(len1 >= 0 || len2 >= 0 || len3 >= 0 || len4 >= 0){
        num = carry;
        if(len1 >= 0) num += a[len1]-'0';
        if(len2 >= 0) num += b[len2]-'0';
        if(len3 >= 0) num += c[len3]-'0';
        if(len4 >= 0) num += d[len4]-'0';
        carry = num/10;
        num %= 10;
        s_res += (num+'0');
        --len1;--len2;--len3;--len4;
    }
    while(carry){
        s_res += (carry%10 + '0');
        carry /= 10;
    }
    reverse(s_res.begin(),s_res.end());
    return s_res;
}
string big_multiply(string a,string b,int n1,int n2){
    string s_result="";
    if((a[0]=='-'&&b[0]!='-')||(a[0]!='-'&&b[0]=='-')) s_result="-";//符号判断
    if(a[0]=='-') a.erase(0);
    if(b[0]=='-') b.erase(0);   
    if(n1 == 1){s_result+=one_mul_n(a,b);return s_result;}//1位乘n位 
    if(n2 == 1){s_result+=one_mul_n(b,a);return s_result;}
    int len1 = (n1+1)/2;
    int len2 = (n2+1)/2;
    string A,B,C,D;
    A.append(a,0,len1);//分治 
    B.append(a,len1,n1-len1);
    C.append(b,0,len2);
    D.append(b,len2,n2-len2);
    string num1 = big_multiply(A,C,len1,len2);
    string num2 = big_multiply(A,D,len1,n2-len2);
    string num3 = big_multiply(B,C,n1-len1,len2);
    string num4 = big_multiply(B,D,n1-len1,n2-len2);
    num1.append(n1-len1+n2-len2,'0');
    num2.append(n1-len1,'0');
    num3.append(n2-len2,'0');
    s_result+=add(num1,num2,num3,num4);
    return s_result;
}