记录编号	221478	评测结果	AAAAAAAAAAAA
题目名称	39.增强的乘法问题	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-01-23 18:23:46	内存使用	27.61 MiB

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
using namespace std;
struct u
{
	double r;
	double i;
}A[530010],B[530010],C[530010];
char s1[530010],s2[530010];
int pr[530010];
int l1,l2,l,n=1,rg;
//#define pi 3.14159265358979
const double pi=acos(-1);
u operator - (u aa,u bb)
{
	return (u){aa.r-bb.r,aa.i-bb.i};
}
u operator + (u aa,u bb)
{
	return (u){aa.r+bb.r,aa.i+bb.i};
}
u operator *(u aa,u bb)
{
	return (u){aa.r*bb.r-aa.i*bb.i,aa.r*bb.i+aa.i*bb.r};
}
inline void gfft(u *a,int b)
{
	for(int i=0,j=0;i<n;i++)
	{
		if(i>j)
			swap(a[i],a[j]);
		for(int t=n>>1;(j^=t)<t;t>>=1);
	}
	int m=2;
	u wn,w,t,uu;
	for(int cs=1;cs<=rg;cs++,m<<=1)
	{
		wn=(u){cos(2.0*pi/m),b*sin(2.0*pi/m)};
		w=(u){1,0};
		for(int i=0;i<n;i+=m,w=(u){1,0})
		{
			for(int k=0,p=m>>1;k<p;k++,w=w*wn)
			{
				t=w*a[i+k+(m>>1)];
				uu=a[i+k];
				a[i+k]=uu+t;
				a[i+k+(m>>1)]=uu-t;
			}
		}
	}
	if(b==-1)
		for(int i=0;i<n;i++)
			a[i].r/=n;
}
int main()
{
	freopen("mul.in","r",stdin);
	freopen("mul.out","w",stdout);
	scanf("%s%s",s1,s2);
	l1=strlen(s1),l2=strlen(s2);
	l=max(l1,l2);
	for(int i=l1-1;i>=0;i--)
		A[l1-i-1].r=s1[i]-'0';
	for(int i=l2-1;i>=0;i--)
		B[l2-i-1].r=s2[i]-'0';
	for(n=1;n<(l<<1);rg++,n<<=1);
	gfft(A,1);
	gfft(B,1);
	for(int i=0;i<n;i++)
		C[i]=A[i]*B[i];
	gfft(C,-1);
	for(int i=0;i<n;i++)
		pr[i]=(int)(C[i].r+0.5);
	for(int i=0;i<n;i++)
		if(pr[i]>9)
		{
			pr[i+1]+=pr[i]/10;
			pr[i]%=10;
		}
	bool p=0;
	for(int i=n;i>=0;i--)
	{
		if(pr[i])
			p=1;
		if(p)
			putchar(pr[i]+48);
	}
	if(!p)
		puts("0");
}