代码

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0;int f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int MAXN = 3000005;
typedef complex<double> cp;
int n,m,l,lim=1,rev[MAXN],ans[MAXN];
cp f[MAXN],g[MAXN];
string str1,str2;

inline void fft(cp *a,int type)
{
	for(register int i=0;i<lim;i++)
        if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(register int mid=1;mid<lim;mid<<=1)
	{
		cp cur(cos(M_PI/mid),type*sin(M_PI/mid));
		for(register int j=0;j<lim;j+=(mid<<1))
		{
			cp w(1,0);
			for(register int k=0;k<mid;++k,w*=cur)
			{
				cp x=a[j+k],y=w*a[j+k+mid];
				a[j+k]=x+y; a[j+k+mid]=x-y;
			}
		}
	}
}

int main()
{
	cin>>str1>>str2; 
    n=str1.length(); m=str2.length();
    for(register int i=n-1;i>=0;--i) f[n-1-i]=str1[i]-'0';
	for(register int i=m-1;i>=0;--i) g[m-1-i]=str2[i]-'0';
	while(lim<=n+m) lim<<=1,l++;
	for(register int i=0;i<lim;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	fft(f,1); fft(g,1);
	for(int i=0;i<=lim;i++)
        f[i]*=g[i];
	fft(f,-1);
	for(int i=0;i<=lim;i++)
    {
        ans[i]+=(int)(f[i].real()/lim+0.5);
		if(ans[i]>=10)
		{
			ans[i+1]+=ans[i]/10,ans[i]%=10;
			if(i==lim) lim++;
		}
    }
    while(!ans[lim] && lim>=1) lim--; lim++;
	for(int i=lim-1;i>=0;i--) printf("%d",ans[i]);
	return 0;
}

评测结果