FFT教你做乘法

 

题目描述

 

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

 

输入

 

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

 

输出

 

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

 

输入样例

 

1 72 17

 

输出样例

 

736 解题思路： 推荐博客（有助于理解FFT）： 推荐博客（FFT之大数相乘）：给出代码：

1 #include 
     
        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
      
       >=1; 36         } 37         if(p
       
        =0?a[j]-'0':0.,0.); 87         for(int i=0,j=lenb-1; i
        
         =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
         
          0&&ans[pos]<=0; --pos) ;104         for(; pos>=0; --pos) printf("%d",ans[pos]);105         printf("\n");106     }107     return 0;108 }