Description
给出两个n位10进制整数x和y，你需要计算x*y。
Input
第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。
Output
输出一行，即x*y的结果。
Sample Input
1
3
4
3
4
Sample Output
12
数据范围：
n<=60000
数据范围：
n<=60000
贴个FFT的板子以后看
http://blog.csdn.net/iamzky/article/details/22712347
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
double pi=acos(-1.0); // PI值
struct complex
{
double r,i;
complex(double real=0.0,double image=0.0)
{
r=real;
i=image;
}
// 以下为三种虚数运算的定义
complex operator +(complex o) const
{
return complex(r+o.r,i+o.i);
}
complex operator -(complex o) const
{
return complex(r-o.r,i-o.i);
}
complex operator *(complex o) const
{
return complex(r*o.r-i*o.i,r*o.i+i*o.r);
}
};
complex a[1000001],b[1000001];
char x1[1000001],x2[1000001];
bool v[1000001];
int sum[1000001];
inline void brc(complex *a,int l) //二进制反转
{
memset(v,false,sizeof(v));
int i;
for(i=1;i<l-1;i++)
{
int x=i,y=0;
int m=(int)log2(l)+0.1;
if(v[x])
continue;
while(m!=0)
{
m--;
y=y*2;
y=(y|(x&1));
x=x/2;
/*y<<=1;
y|=(x&1);
x>>=1;*/
}
v[i]=true;
v[y]=true;
swap(a[i],a[y]);
}
}
inline void fft(complex *y,int l,double on)
{
int i,j,k;
complex u,t;
brc(y,l);//二进制反转
for(i=2;i<=l;i=i*2)
{
complex wn(cos(on*2*pi/i),sin(on*2*pi/i));
for(j=0;j<l;j+=i)
{
complex w(1,0);
for(k=j;k<j+i/2;k++)
{
u=y[k];
t=w*y[k+i/2];
y[k]=u+t;
y[k+i/2]=u-t;
w=w*wn;
}//蝴蝶操作
}
}
if(on==-1)
{
for(i=0;i<l;i++)
y[i].r/=l;//IDFT
}
}
int main()
{
scanf("%s%s",x1,x2);
int la=strlen(x1),lb=strlen(x2);
int l=1;
while(l<la*2||l<lb*2)
l=l*2;
int i;
for(i=0;i<la;i++) // 倒置存入
{
a[i].r=x1[la-i-1]-'0';
a[i].i=0.0;
}
for(i=la;i<l;i++)
{
a[i].r=0.0;
a[i].i=0.0;
}
for(i=0;i<lb;i++)
{
b[i].r=x2[lb-i-1]-'0';
b[i].i=0.0;
}
for(i=lb;i<l;i++)
{
b[i].r=0.0;
b[i].i=0.0;
}
fft(a,l,1);//DFT
fft(b,l,1);//DFT
for(i=0;i<l;i++)
a[i]=a[i]*b[i];
fft(a,l,-1);//IDFT
for(i=0;i<l;i++)
sum[i]=a[i].r+0.5;
for(i=0;i<l;i++)
{
sum[i+1]+=sum[i]/10;
sum[i]%=10;
}
l=la+lb-1;
while(sum[l]==0)
l--;
for(i=l;i>=0;i--)
printf("%d",sum[i]);
printf("\n");
// }
return 0;
}