题解 P1919 【【模板】A*B Problem升级版（FFT快速傅里叶）】

· · 题解

介绍一种并不能过题的Karatsuba 乘法。

假设我们要求x*y,我们让：

x=a*10^{n/2}+b,y=c*10^{n/2}+d

那么

xy=ac\times10^{(n-n/2)\times2}+(ad+bc)\times10^{n-n/2}+bd

又因为

ad+bc=(a+b)(c+d)-(ac+bd)

所以我们可以重复利用ac和bd的结果，不用做四次乘法。 这样递归下去求的复杂度是 (来自百度百科)

3n^{log3}≈3n^{1.585}

下面是这个算法本蒟蒻的代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int L=120010;
string add(string a,string b)
{
    string ans;
    int na[L]={0},nb[L]={0};
    int la=a.size(),lb=b.size();
    for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
    for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
    int lmax=la>lb?la:lb;
    for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;
    if(na[lmax]) lmax++;
    for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
    return ans;
}
string sub(string a,string b)
{
    string ans;
    int na[L]={0},nb[L]={0};
    int la=a.size(),lb=b.size();
    for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
    for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
    int lmax=la>lb?la:lb;
    for(int i=0;i<lmax;i++)
    {
        na[i]-=nb[i];
        if(na[i]<0) na[i]+=10,na[i+1]--;
    }
    while(!na[--lmax]&&lmax>0)  ;lmax++;
    for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
    return ans;
}
//---------------------大数加减法---------------------------------//
string karatsuba(string a,string b){
    if(a.size()<b.size()) swap(a,b);
    int tmp=a.size()-b.size();
    string qd0="";for(int i=0;i<tmp;i++) qd0+='0';
    b=qd0+b;
    //---------------补前导0------------------//
    if(a.size()==b.size()&&a.size()==1){
        string ans="";
        int ansnum=(a[0]-48)*(b[0]-48);
        while(ansnum){ans=(char)('0'+ansnum%10)+ans;ansnum/=10;}
        if(ans.size()==0) ans="0";
        return ans;
    }
    int mid=a.size()-a.size()/2;
    string qa,ha,qb,hb;
    qa=a.substr(0,mid);ha=a.substr(mid,a.size()-mid);
    qb=b.substr(0,mid);hb=b.substr(mid,b.size()-mid);
    string qaqb=karatsuba(qa,qb);
    string hahb=karatsuba(ha,hb);
    string qahbhaqb=sub(karatsuba(add(qa,ha),add(qb,hb)),add(qaqb,hahb));
    //------------------三次乘法---------------------------//
    for(int i=0;i<(a.size()-mid)*2;i++) qaqb+='0';
    for(int i=0;i<(a.size()-mid);i++) qahbhaqb+='0';
    //------------------移位------------------------------//
    string ans=add(qaqb,qahbhaqb);
    ans=add(ans,hahb);
    return ans;
}
int main(){
    int n;cin>>n;
    string a,b;cin>>a>>b;
    cout<<karatsuba(a,b)<<endl;
    return 0;
}