参考这里：http://www.cnblogs.com/pdev/p/4354705.html

 　　　　  http://www.cnblogs.com/pdev/p/4354629.html

 

题意：求大数乘法A*B

A和B位数很长。裸高精度时间复杂度是O(nm)，会完蛋

 

不妨回忆下裸高精度的过程：

 

其实乘法的那一步很类似前面介绍过的多项式快速乘法诶(⊙▽⊙)

所以就可以用前述方法计算咯，时间复杂度O(nlogn)

 

我是这样理解的：

每个乘数都是都是一坨时域信号（一个大混合物），然后对乘数分别进行DFT（Discrete Fourier Transform）得到频域信号（一堆纯净物）。

然后对纯净物按类别分别相加，就得到了新信号（这里即乘法结果）对应的频域信号（一堆纯净物）

然后再来一次IDFT（Inverse DFT，逆变换）把频域再转成时域（一个大混合物，即真正的乘法结果）就好啦

 

总结一下本题的模式：

　　读入向量x、y

　　int len=1;　　while(len < lx*2 || len < ly*2)len<<=1;　　　　(lx、ly分别是向量x和y的长度)

　　fft(x)，fft(y)

　　for i=0 to len-1　　　　x[i]=x[i]*y[i]

　　ifft(x)

　　for(int i = 0; i < len; i++)　　sum[i] = (int)(X[i].x+0.5);　　　　变回整数

 

 

1 #include  
      
         2 #include  
       
          3 #include  
        
           4 #include  
         
            5 #include  
          
             6 using namespace  std;  7 const double PI = acos(-1.0);  8 //复数结构体  9 struct  Complex 10 { 11     double x,y;//实部和虚部  x+yi 12     Complex(double _x = 0.0,double _y = 0.0) 13     { 14         x = _x; 15         y = _y; 16     } 17     Complex operator -(const Complex &b)const 18     { 19         return  Complex(x-b.x,y-b.y); 20     } 21     Complex operator +(const Complex &b)const 22     { 23         return  Complex(x+b.x,y+b.y); 24     } 25     Complex operator *(const Complex &b)const 26     { 27         return  Complex(x*b.x-y*b.y,x*b.y+y*b.x); 28     } 29 }; 30  31 void change(Complex y[],int  len) 32 { 33     int  i,j,k; 34     for(i = 1, j = len/2; i 
           
            = k) 41 { 42 j -= k; 43 k /= 2; 44 } 45 if(j < k)j += k; 46 } 47 } 48 49 50 void fft(Complex y[],int len,int on) 51 { 52 change(y,len); 53 for(int h = 2; h <= len; h <<= 1) 54 { 55 Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h)); 56 for(int j = 0; j < len; j+=h) 57 { 58 Complex w(1,0); 59 for(int k = j; k < j+h/2; k++) 60 { 61 Complex u = y[k]; 62 Complex t = w*y[k+h/2]; 63 y[k] = u+t; 64 y[k+h/2] = u-t; 65 w = w*wn; 66 } 67 } 68 } 69 if(on == -1) 70 for(int i = 0; i < len; i++) 71 y[i].x /= len; 72 } 73 74 75 const int MAXN = 200010; 76 Complex x1[MAXN],x2[MAXN]; 77 char str1[MAXN/2],str2[MAXN/2]; 78 int sum[MAXN]; 79 int main() 80 { 81 while(scanf("%s%s",str1,str2)==2) 82 { 83 int len1 = strlen(str1); 84 int len2 = strlen(str2); 85 int len = 1; 86 while(len < len1*2 || len < len2*2)len<<=1; 87 for(int i = 0; i < len1; i++) 88 x1[i] = Complex(str1[len1-1-i]-'0',0); 89 for(int i = len1; i < len; i++) 90 x1[i] = Complex(0,0); 91 for(int i = 0; i < len2; i++) 92 x2[i] = Complex(str2[len2-1-i]-'0',0); 93 for(int i = len2; i < len; i++) 94 x2[i] = Complex(0,0); 95 //x1[i]:x1对应的向量 96 //例如1989就是(9,0)、(8,0)、(9,0)、(1,0)、(0,0)、... 97 98 99 fft(x1,len,1);100 fft(x2,len,1);101 102 for(int i = 0; i < len; i++)103 x1[i] = x1[i]*x2[i];104 105 fft(x1,len,-1);106 107 for(int i = 0; i < len; i++)108 sum[i] = (int)(x1[i].x+0.5);109 /*110 for(int i=0;i
            
              0)len--;121 for(int i = len; i >= 0; i--)122 printf("%c",sum[i]+'0');123 printf("\n");124 }125 return 0;126 }