记录编号	239887	评测结果	AAAAAAAEEE
题目名称	超强的乘法问题	最终得分	70
用户昵称	0	是否通过	未通过
代码语言	C++	运行时间	0.612 s
提交时间	2016-03-20 19:37:47	内存使用	19.40 MiB

#include<cstdio>
#include<complex>
#include<cstring>
#include<cstdlib>
 
#define maxn 600010
 
using namespace std;
 
typedef complex<double> Ex;
double pi=acos(-1);
int n,m;
char s[maxn];
Ex a[maxn],b[maxn];
 
void fft(Ex* x,int n,int k)
{
	if(n==1) return;
	Ex l[n>>1],r[n>>1];
	for(int i=2;i<=n;i+=2)
		l[i>>1]=x[i-1],r[i>>1]=x[i];
	fft(l,n>>1,k),fft(r,n>>1,k);
	Ex wn(cos(2*pi/n),sin(2*k*pi/n)),w(1,0),t;
	for(int i=1;i<=n>>1;i++,w*=wn)
		t=w*r[i],x[i]=l[i]+t,x[i+(n>>1)]=l[i]-t;
	return ;
}
 
int main()
{
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	scanf("%s",s+1);n=strlen(s+1);
	for(int i=1;i<=n;i++) a[i]=s[n-i+1]-'0';
	scanf("%s",s+1);m=strlen(s+1);
	for(int i=1;i<=m;i++) b[i]=s[m-i+1]-'0';
	m=n+m;for(n=1;n<=m;n<<=1);
	fft(a,n,1),fft(b,n,1);
	for(int i=1;i<=n;i++) a[i]=a[i]*b[i];
	fft(a,n,-1);
	int ans[maxn];memset(ans,0,sizeof(ans));
	for(int i=1;i<=n;i++) ans[i]=a[i].real()/n+0.5;
	for(int i=1;i<=m;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;
	while(!ans[m]) m--;
	for(int i=m;i>0;i--) printf("%d",ans[i]);
	return 0;
	
}