代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2100086;
const double pi=acos(-1);
inline int read()
{
	int x=0,k=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*k;
}
struct comp{
	double r,i;
	comp(double aa=0,double bb=0){r=aa,i=bb;}
	comp operator+(comp z){return comp(r+z.r,i+z.i);}
	comp operator-(comp z){return comp(r-z.r,i-z.i);}
	comp operator*(comp z){return comp(r*z.r-i*z.i,r*z.i+i*z.r);}
}a[MAXN],b[MAXN];
int N,n,m,q,r[MAXN],c[MAXN];
string x,y;
void DFT(comp *A,int type)
{
	rep(i,0,N-1)if(i<r[i])swap(A[i],A[r[i]]);
	for(int i=1;i<N;i<<=1)
	{
		int R=i<<1;
		comp wn(cos(pi/i),type*sin(pi/i));
		for(int j=0;j<N;j+=R)
		{
			comp w(1,0);
			for(int k=j;k<=j+i-1;k++)
			{
				comp x=A[k],y=A[k+i]*w;
				A[k]=x+y,A[k+i]=x-y;
				w=w*wn;
			}
		}
	}
}
int main()
{
	cin>>x>>y;
	n=x.length()-1,m=y.length()-1;
	for(N=1;N<n+m+1;N<<=1,q++);
	rep(i,0,n)a[i].r=(double)(x[n-i]-'0');
	rep(i,0,m)b[i].r=(double)(y[m-i]-'0');
	rep(i,0,N-1)r[i]=(r[i>>1]>>1)|((i&1)<<(q-1));
	DFT(a,1);
	DFT(b,1);
	rep(i,0,N)a[i]=a[i]*b[i];
	DFT(a,-1);
	rep(i,0,n+m)c[i]=(int)(a[i].r/N+0.5);
	int len=n+m+1;
	rep(i,0,len-1)
	{
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	while(len>0&&!c[len])len--;
	per(i,len,0)printf("%d",c[i]);
	//printf("%d ",(int)(a[i].r/N+0.5));
	return 0;
}

评测结果