题目描述
给出两个n位10进制整数x和y,你需要计算x*y。
输入输出格式
输入格式:
第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。
输出格式:
输出一行,即x*y的结果。(注意判断前导0)
输入输出样例
输入样例#1: CYaRon耗时5分钟完成数据制作。
emmmm感觉学了FFT没什么乱用啊,,
也就来水一水这种板子吧。
思路很简单,将每一位看成多项式的系数。
来一遍FFT
最后去掉前导0
输出
不过话说我的FFT怎么这么慢
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=1e5+;
const double Pi=acos(-1.0);
int r[MAXN],l=,limit=,c[MAXN];
char sa[MAXN],sb[MAXN];
struct complex
{
double x,y;
complex(double xx=,double yy=){x=xx,y=yy;}
}a[MAXN],b[MAXN];
complex operator + (complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator - (complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator * (complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
void FFT(complex *a,int type)
{
for(int i=;i<limit;i++)
if(i<r[i])
swap(a[i],a[r[i]]);
for(int mid=;mid<limit;mid<<=)
{
complex Wn(cos(Pi/mid),type*sin(Pi/mid) );
for(int R=mid<<,j=;j<limit;j+=R)
{
complex w(,);
for(int k=;k<mid;k++,w=w*Wn)
{
complex x=a[j+k],y=w*a[j+k+mid];
a[j+k]=x+y;
a[j+k+mid]=x-y;
}
}
}
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
int N;
scanf("%d",&N);N--;
scanf("%s%s",sa,sb);
for(int i=;i<=N;i++) a[i].x=sa[N-i]-'',b[i].x=sb[N-i]-'';
while(limit<=N*)
limit<<=,l++;
for(int i=;i<=limit;i++) r[i]=(r[i>>]>>) | ((i&)<<(l-) );
FFT(a,);
FFT(b,);
for(int i=;i<=limit;i++) a[i]=a[i]*b[i];
FFT(a,-);
for(int i=;i<=limit;i++) c[i]=(int)(a[i].x/limit+0.5);
//for(int i=1;i<=limit;i++) printf("%d ",c[i]);printf("\n");
for(int i=;i<=limit;i++)
{
if(c[i]>)
{
c[i+]+=c[i]/,c[i]%=;
if(i+>limit) limit++;
}
}
for(int i=limit;i>=;i--)
if(c[i]==) limit--;
else break;
for(int i=limit;i>=;i--)
printf("%d",c[i]);
return ;
}