HDU 1402 A * B Problem Plus 快速傅里叶变换 FFT 多项式

http://acm.hdu.edu.cn/showproblem.php?pid=1402

快速傅里叶变换优化的高精度乘法。

https://blog.csdn.net/ggn_2015/article/details/68922404 这个写的很详细了。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<iostream>

 #include<vector>

 #include<complex>

 using namespace std;

 #define LL long long

 const int maxn=;

 typedef complex< double >cd;

 char s1[maxn]={},s2[maxn]={};

 int ans[maxn]={};

 int rev[maxn]={}; int s,bit;

 cd a[maxn]={},b[maxn]={};

 double Pi;

 inline void getrev(){ for(int i=;i<s;i++)rev[i]=(rev[i>>]>>)|((i&)<<(bit-)); }

 inline void fft(cd *c,int n,int dft){

     for(int i=;i<=s;i++)if(rev[i]>i)swap(c[i],c[rev[i]]);

     for(int step=;step<n;step<<=){

         cd shu=exp(cd(,dft*Pi/step));

         for(int i=;i<n;i+=step<<){

             cd z=cd(,);

             for(int j=i;j<i+step;j++){

                 cd x=c[j];cd y=c[j+step]*z;

                 c[j]=x+y; c[j+step]=x-y;

                 z*=shu;

             }

         }

     }

     if(dft==-)for(int i=;i<n;i++)c[i]/=n;

 }

 int main(){

     cd cle(,);Pi=2.0*acos(0.0);

     while(~scanf("%s%s",s1,s2)){

         memset(rev,,sizeof(rev));

         int l1=strlen(s1),l2=strlen(s2),n=l1+l2-;

         bit=;s=; for(;s<n;++bit)s<<=;

         getrev();

         for(int i=;i<=s;i++){a[i]=cle;b[i]=cle;}

         for(int i=;i<l1;i++)a[i]=(double)(s1[l1-i-]-'');

         for(int i=;i<l2;i++)b[i]=(double)(s2[l2-i-]-'');

         fft(a,s,);fft(b,s,);

         for(int i=;i<s;i++)a[i]*=b[i];

         fft(a,s,-);

         memset(ans,,sizeof(ans));

         for(int i=;i<s;i++){

             ans[i]+=(int)(a[i].real()+0.5);

             ans[i+]+=ans[i]/;

             ans[i]%=;

         }

         int i;

         for(i=l1+l2;!ans[i]&&i>;--i);

         if(i==)printf("%d\n",ans[]);

         else{

             for(;i>=;--i)printf("%d",ans[i]);

             printf("\n");

         }

     }

     return ;

 }