| 比赛 | 
    清华集训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;
}