比赛 清华集训2017模板练习 评测结果 AAAAAAAAAA
题目名称 超强的乘法问题 最终得分 100
用户昵称 栋霸霸 运行时间 1.941 s
代码语言 C++ 内存使用 51.81 MiB
提交时间 2017-07-17 14:21:56
显示代码纯文本
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cmath>
#include <complex>
using namespace std;

const int N=1000000;

typedef complex<double> c;
c F[N],A[N],B[N];
char a[N],b[N];
int ans[N];

int rev(int x,int n)
{
	int ret=0;
	for(int i=0; (1<<i)<n; i++)ret=(ret<<1)|((x&(1<<i))>0);
	return ret;
}

void fft(c *a,int n,int f)
{
	for(int i=0; i<n; i++)F[rev(i,n)]=a[i];
	for(int i=2; i<=n; i*=2)
	{
		c wn=c(cos(2*acos(-1)*f/i),sin(2*acos(-1)*f/i));
		for(int j=0; j<n; j+=i)
		{
			c w=1;
			for(int k=j; k<j+i/2; k++)
			{
				c u=F[k],t=w*F[k+i/2];
				F[k]=u+t;
				F[k+i/2]=u-t;
				w*=wn;
			}
		}
	}
	for(int i=0; i<n; i++)a[i]=(F[i]/=(f==-1?n:1));
}


int main()
{
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	scanf("%s%s",a,b);
	int l1=strlen(a),l2=strlen(b),n1=1,n2=1,n=1;
	while(n1<=l1)n1*=2;
	while(n2<=l2)n2*=2;
	while(n<2*max(n1,n2))n*=2;
	for(int i=0; i<n; i++)A[i]=(i<l1?a[l1-i-1]-'0':0);
	for(int i=0; i<n; i++)B[i]=(i<l2?b[l2-i-1]-'0':0);
	fft(A,n,1);
	fft(B,n,1);
	for(int i=0; i<n; i++)A[i]*=B[i];
	fft(A,n,-1);
	for(int i=0; i<n; i++)ans[i]=int(A[i].real()+0.5);
	for(int i=0; i<n-1; i++)ans[i+1]+=ans[i]/10,ans[i]%=10;
	bool f=0;
	for(int i=n-1; i>=0; i--)ans[i]?printf("%d",ans[i]),f=1:f||!i?printf("0"):0;
}