记录编号	532624	评测结果	AAAAAAAAAA
题目名称	超强的乘法问题	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.469 s
提交时间	2019-05-31 21:02:15	内存使用	51.81 MiB

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+10;
const double PI=acos(-1.0);
struct complex
{
	double x,y;
	complex(double xx=0,double yy=0) {x=xx,y=yy;}
} a[N],b[N];
complex operator + (complex a,complex b) {return complex(a.x+b.x,a.y+b.y);}
complex operator - (complex a,complex b) {return complex(a.x-b.x,a.y-b.y);}
complex operator * (complex a,complex b) {return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
int m,n,limit=1,l,r[N],ans[N];
void FFT(complex *A,int type)
{
	for (int i=0;i<limit;i++)
		if (i<r[i]) swap(A[i],A[r[i]]);
	for (int mid=1;mid<limit;mid<<=1)
	{
		complex Wn(cos(PI/mid),type*sin(PI/mid));
		for (int R=mid<<1,j=0;j<limit;j+=R)
		{
			complex w(1,0);
			for (int k=0;k<mid;k++,w=w*Wn)
			{
				complex x=A[j+k],y=w*A[j+k+mid];
				A[j+k]=x+y;
				A[j+k+mid]=x-y;
			}
		}
	}
}
int main()
{
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	char s[N],ss[N];scanf("%s%s",s,ss);
	n=strlen(s),m=strlen(ss);
	for (int i=0;i<n;i++) a[i].x=s[i]-'0';
	for (int i=0;i<m;i++) b[i].x=ss[i]-'0';
	while (limit<=m+n) limit<<=1,l++;
	for (int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	FFT(a,1);FFT(b,1);
	for (int i=0;i<=limit;i++) a[i]=a[i]*b[i];
	FFT(a,-1);
	for (int i=0;i<=n+m;i++) ans[i+1]=(int)(a[i].x/limit+0.5);
	for (int i=n+m;i>=0;i--)
	ans[i-1]+=ans[i]/10,ans[i]=ans[i]%10;
	if (ans[0]) printf("%d",ans[0]);
	for (int i=1;i<=n+m-1;i++) printf("%d",ans[i]);
	return 0;
}