比赛 清华集训2017模板练习 评测结果 AAAAAAAAAA
题目名称 超强的乘法问题 最终得分 100
用户昵称 再见 运行时间 0.490 s
代码语言 C++ 内存使用 34.14 MiB
提交时间 2017-07-17 17:39:02
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
const double pi=acos(-1)*2;

struct cp{
	double a,b;
	cp(double _a=0,double _b=0){ a=_a; b=_b; }
	cp operator+(cp &x){ return cp(a+x.a,b+x.b); }
	cp operator-(cp &x){ return cp(a-x.a,b-x.b); }
	cp operator*(cp &x){ return cp(a*x.a-b*x.b,a*x.b+b*x.a); }
}a[1000010],b[1000010];

inline cp swap(cp &a,cp &b){
	cp c=a; a=b; b=c;
}

void FFT(cp *a,int N,int f){
	for(int i=0,j=0;i<N;i++){
		if(i<j) swap(a[i],a[j]);
		for(int l=N>>1;(j^=l)<l;l>>=1);
	}
	for(int i=2;i<=N;i<<=1){
		cp wn(cos(pi/i),f?-sin(pi/i):sin(pi/i));
		for(int j=0,m=i>>1;j<N;j+=i){
			cp w(1,0);
			for(int k=0;k<m;k++){
				cp x=a[j+k+m]*w;
				a[j+k+m]=a[j+k]-x;
				a[j+k]=a[j+k]+x;
				w=w*wn;
			}
		}
	}
	if(f)
		for(int i=0;i<N;i++) a[i].a/=N;
}

int n,m,out[800010];
char str[300010];

int main(){
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	scanf("%s",str+1); n=strlen(str+1);
	for(int i=0;i<n;i++) a[i].a=str[n-i]-'0';
	scanf("%s",str+1); m=strlen(str+1);
	for(int i=0;i<m;i++) b[i].a=str[m-i]-'0';
	int N=1; for(N;N<n+m;N<<=1);
	FFT(a,N,0); FFT(b,N,0);
	for(int i=0;i<N;i++) a[i]=a[i]*b[i];
	FFT(a,N,1);
	for(int i=0;i<=n+m;i++) out[i]=(int)round(a[i].a);
	for(int i=0;i<=n+m;i++) out[i+1]+=out[i]/10,out[i]%=10;
    int l=n+m;	while(out[l+1]) l++,out[l+1]+=out[l]/10,out[l]%=10;
	while(!out[l]&&l>=1) l--;
	for(int i=l;i>=0;i--)
		printf("%d",out[i]);
	putchar('\n');
	return 0;
}