A * B Problem Plus

 1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 using namespace std; 6 #define N 50500*2 7 const double PI=acos(-1.0); 8 struct Vir 9 {10     double re,im;11     Vir(double _re=0.,double _im=0.):re(_re),im(_im){}12     Vir operator*(Vir r) { return Vir(re*r.re-im*r.im,re*r.im+im*r.re);}13     Vir operator+(Vir r) { return Vir(re+r.re,im+r.im);}14     Vir operator-(Vir r) { return Vir(re-r.re,im-r.im);}15 };16 void bit_rev(Vir *a,int loglen,int len)17 {18     for(int i=0;i<len;++i)19     {20         int t=i,p=0;21         for(int j=0;j<loglen;++j)22         {23             p<<=1;24             p=p|(t&1);25             t>>=1;26         }27         if(p<i)28         {29             Vir temp=a[p];30             a[p]=a[i];31             a[i]=temp;32         }33     }34 }35 void FFT(Vir *a,int loglen,int len,int on)36 {37     bit_rev(a,loglen,len);38 39     for(int s=1,m=2;s<=loglen;++s,m<<=1)40     {41         Vir wn=Vir(cos(2*PI*on/m),sin(2*PI*on/m));42         for(int i=0;i<len;i+=m)43         {44             Vir w=Vir(1.0,0);45             for(int j=0;j<m/2;++j)46             {47                 Vir u=a[i+j];48                 Vir v=w*a[i+j+m/2];49                 a[i+j]=u+v;50                 a[i+j+m/2]=u-v;51                 w=w*wn;52             }53         }54     }55     if(on==-1)56     {57         for(int i=0;i<len;++i){58           a[i].re/=len;59           a[i].im/=len;60         }61     }62 }63 char a[N*2],b[N*2];64 Vir pa[N*2],pb[N*2];65 int ans[N*2];66 int main ()67 {68     while(scanf("%s%s",a,b)!=EOF)69     {70         int lena=strlen(a);71         int lenb=strlen(b);72         int n=1,loglen=0;73         while(n<lena+lenb) n<<=1,loglen++;74         for(int i=0,j=lena-1;i<n;++i,--j)75             pa[i]=Vir(j>=0?a[j]-‘0‘:0.,0.);76         for(int i=0,j=lenb-1;i<n;++i,--j)77             pb[i]=Vir(j>=0?b[j]-‘0‘:0.,0.);78          memset(ans,0,sizeof(int)*(n+1));79         FFT(pa,loglen,n,1);80         FFT(pb,loglen,n,1);81         for(int i=0;i<n;++i)82             pa[i]=pa[i]*pb[i];83         FFT(pa,loglen,n,-1);84 85         for(int i=0;i<n;++i)86             ans[i]=pa[i].re+0.5;87         for(int i=0;i<n;++i)88         {89              ans[i+1]+=ans[i]/10;90              ans[i]%=10;91         }92         int pos=lena+lenb-1;93         for(;pos>0&&ans[pos]<=0;--pos) ;94         for(;pos>=0;--pos)95             printf("%d",ans[pos]);96         puts("");97     }98     return 0;99 }