FFT教你做乘法

题目描述

给定两个8进制正整数A和B（A和B均小于10000位），请利用离散傅里叶变换计算A与B的乘积。

输入

多组测试数据（组数不超过100）每组测试数据只有一行，包含两个正整数A和B。

输出

对于每组数据，输出一行，为A和B的乘积。

输入样例

1 7
2 17

输出样例

7
36

解题思路：
推荐博客（有助于理解FFT）：http://blog.jobbole.com/58246/
推荐博客（FFT之大数相乘）：http://www.cnblogs.com/lsx54321/archive/2012/07/20/2601632.html
给出代码：

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