代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e4+5;
const double PI=acos(-1.0);
struct Complex{
    double real,imag;
    Complex(double a=0,double b=0):real(a),imag(b){}
    Complex(const Complex &a):real(a.real),imag(a.imag){}
    Complex conj()const{return Complex(real,-imag);}
    Complex &operator=(const Complex &a){real=a.real,imag=a.imag;return *this;}
    Complex &operator+=(const Complex &a){real+=a.real,imag+=a.imag;return *this;}
    Complex &operator-=(const Complex &a){real-=a.real,imag-=a.imag;return *this;}
    Complex &operator*=(const Complex &a){double tmp1=real*a.real-imag*a.imag,tmp2=real*a.imag+imag*a.real;real=tmp1,imag=tmp2;return *this;}
    Complex &operator/=(const Complex &a){double tmp1=(real*a.real+imag*a.imag)/(a.real*a.real+a.imag*a.imag),tmp2=(imag*a.real-real*a.imag)/(a.real*a.real+a.imag*a.imag);real=tmp1,imag=tmp2;return *this;}
    friend Complex operator+(const Complex &a,const Complex &b){Complex c(a);return c+=b;}
    friend Complex operator-(const Complex &a,const Complex &b){Complex c(a);return c-=b;}
    friend Complex operator*(const Complex &a,const Complex &b){Complex c(a);return c*=b;}
    friend Complex operator/(const Complex &a,const Complex &b){Complex c(a);return c/=b;}
}eps[N],a[N],b[N];
void init(int n){
    int l=n>>1;
    for(int i=0;i<l;++i){
        eps[l+i].real=cos(i*PI/l);
        eps[l+i].imag=sin(i*PI/l);
    }
    while(l>>=1){
        for(int i=0;i<l;++i){
            eps[l+i]=eps[l+i<<1];
        }
    }
}
void dft(int n,Complex x[]){
    for(int i=0,j=0;i<n;++i){
        if(i<j)swap(x[i],x[j]);
        for(int k=n>>1;(j^=k)<k;k>>=1){}
    }
    for(int i=2;i<=n;i<<=1){
        int l=i>>1;
        for(int j=0;j<n;j+=i){
            for(int k=0;k<l;++k){
                Complex u=x[k+j],v=eps[l+k]*x[k+j+l];
                x[k+j]=u+v;
                x[k+j+l]=u-v;
            }
        }
    }
}
void idft(int n,Complex x[]){
    reverse(x+1,x+n);
    dft(n,x);
    for(int i=0;i<n;++i)x[i]/=n;
}
char t[N<<2];
int main(){
#ifdef LOCAL
    freopen("..\\in","r",stdin),freopen("..\\out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    const int block=5; // 压位
    cin>>(t+1);
    int len1=strlen(t+1); // 字符串长度
    for(int i=len1,j=0;i>0;i-=block,++j){
        for(int k=block-1;~k;--k){
            if(i-k>0){
                a[j]=a[j]*10+t[i-k]-'0';
            }
        }
    }
    cin>>(t+1);
    int len2=strlen(t+1); // 字符串长度
    for(int i=len2,j=0;i>0;i-=block,++j){
        for(int k=block-1;~k;--k){
            if(i-k>0){
                b[j]=b[j]*10+t[i-k]-'0';
            }
        }
    }
    int len=1;
    while(len<(len1+len2-1)/block+1)len<<=1; // 这边是压位后的长度
    init(len);
    dft(len,a);
    dft(len,b);
    for(int i=0;i<len;++i){
        a[i]*=b[i];
    }
    idft(len,a);
    int top=0; // 将t想象成一个栈，存放答案
    ll tmp=0;
    for(int i=0;i<(len1+len2-1)/block||tmp;++i){
        tmp+=static_cast<ll>(a[i].real+0.5);
        ll j=tmp%100000; // 压多少位这边多少个0
        for(int i=1;i<=block;++i){
            t[top++]=j%10+'0';
            j/=10;
        }
        tmp/=100000; // 压多少位这边多少个0
    }
    while(top&&t[top-1]=='0')--top; // 去前导0
    if(!top)cout<<'0';
    while(top)cout<<t[--top];
    return 0;
}

评测结果