记录编号	296326	评测结果	AAAAAAAATT
题目名称	超强的乘法问题	最终得分	80
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	3.063 s
提交时间	2016-08-15 13:46:20	内存使用	36.13 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
const double PI=acos(-1.0),eps=1e-6;
using namespace std;
const int N=800010,Base=10;
char str[N];int a[N];
struct complex{
	double x,y;
	complex(double _x=0,double _y=0){x=_x;y=_y;}
	complex operator + (const complex &a){return complex(x+a.x,y+a.y);}
	complex operator - (const complex &a){return complex(x-a.x,y-a.y);}
	complex operator * (const complex &a){return complex(x*a.x-y*a.y,x*a.y+y*a.x);}
	complex operator / (const double &a){return complex(x/a,y/a);}
	complex operator * (const double &a){return complex(x*a,y*a);}
};
struct expr{
	int n;
	complex s[N];
	void read(){
		scanf("%s",str);
		n=strlen(str);
		for (int i=0;i<n;i++) s[i]=complex(str[n-i-1]-'0',0);
	}
	void print(){
		int len;
		for (int i=0;i<n;i++) a[i]=int(s[i].x+0.5);
		for (len=0;len<n||a[len];len++)
			a[len+1]+=a[len]/Base,a[len]%=Base;
		while (len>1&&!a[len-1]) len--;
		for (int i=0;i<len;i++) str[i]=a[len-i-1]+'0';
		str[len]=0;
		puts(str);
	}
	void Rader_Transform(){
		int j=0,k;
		for (int i=0;i<n;i++){
			if (j>i) swap(s[i],s[j]);
			k=n;while (j&(k>>=1)) j&=~k;j|=k;
		}
	}
	void FFT(bool type){
		Rader_Transform();
		double pi=type?PI:-PI;
		for (int step=1;step<n;step<<=1){
			for (int H=0;H<n;H+=step<<1){
				double alpha=pi/step;
				complex wn(cos(alpha),sin(alpha)),wk(1.0,0.0);
				for (int k=0;k<step;k++){
					int Ek=H+k,Ok=H+k+step;
					complex t=wk*s[Ok];
					s[Ok]=s[Ek]-t;
					s[Ek]=s[Ek]+t;
					wk=wk*wn;
				}
			}	
		}
		if (!type) for (int i=0;i<n;i++) s[i]=s[i]/n;
	}
	void operator *= (expr &x){
		int S=1;while (S<n+x.n) S<<=1;
		n=x.n=S;
		FFT(1);x.FFT(1);
		for (int i=0;i<n;i++) s[i]=s[i]*x.s[i];
		FFT(0);
	}
}A,B;

int main()
{
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	A.read();B.read();
	A*=B;A.print();
	return 0;
}