记录编号	162920	评测结果	AAAAAAAAAA
题目名称	1473.超强的乘法问题	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	2.364 s
提交时间	2015-05-21 19:42:14	内存使用	26.36 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <complex>

#define Ex complex<double>
#define pi acos(-1)
#define N (1<<19)+10

using namespace std;

int R[N],n1,n2,m,num[N];
Ex a[N],b[N],c[N];

void fft(Ex x[],int n,int t){
	for(int i=0;i<n;i++) if(i<R[i]) swap(x[i],x[R[i]]);
	for(int m=1;m<n;m<<=1){
		Ex wn(cos(pi/m*t),sin(pi/m*t));
		for(int k=0;k<n;k+=(m<<1)){
			Ex wt(1,0);
			for(int i=0;i<m;i++,wt*=wn){
				Ex &A=x[k+m+i],&B=x[k+i],t=wt*A;
				A=B-t; B=B+t;
			}
		}
	}
	if(t==-1) for(int i=0;i<=n;i++) x[i]/=n;
}

char S1[N],S2[N];

int main(){
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	scanf("%s%s",S1,S2);
	n1=strlen(S1);
	n2=strlen(S2);
	for(int i=0;i<n1;i++) a[i]=S1[n1-i-1]-'0';
	for(int i=0;i<n2;i++) b[i]=S2[n2-i-1]-'0';
	m=n1+n2;
	int L=0,n;
	for(n=1;n<=m;n<<=1) L++;
	for(int i=0;i<n;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
	fft(a,n,1); fft(b,n,1);
	for(int i=0;i<n;i++) c[i]=a[i]*b[i];
	fft(c,n,-1);
	for(int i=0;i<m;i++) num[i]=(int)(c[i].real()+0.5);
	for(int i=0;i<m;i++)
		if(num[i]>=10) num[i+1]+=num[i]/10,num[i]%=10;
	for(;num[m];m++)
		if(num[m]>=10) num[m+1]+=num[m]/10,num[m]%=10;
	for(;m>1&&!num[m-1];m--);
	for(int i=m-1;~i;i--) printf("%d",num[i]);
	putchar('\n');
	return 0;
}