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