A * B Problem Plus(fft)

showproblem.php?pid=1402

hdu_1402:A * B Problem Plus

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15419 Accepted Submission(s): 3047

Problem Description

Calculate A * B.

Input

Each line will contain two integers A and B. Process to end of file.

Note: the length of each integer will not exceed 50000.

Output

For each case, output A * B in one line.

Sample Input

1 2 1000 2

Sample Output

2 2000

Author

DOOM III

题解：练习用fft实现大数的乘法达到O(nlog(n))的算法,两个数相乘看成是两个多项式的乘法，这样多项式中的x=10,fft套用模板即可

给出代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cmath>
  5 using namespace std;
  6 const int MAX=300005;
  7 const double PI=acos(-1.0),eps=1e-8;;
  8 double cof1[MAX], cof2[MAX];
  9 int n, k, permutation[MAX];
 10 char s1[MAX],s2[MAX];
 11 int ans[MAX];
 12 struct complex {//复数
 13     double r, v;
 14     complex operator + (complex& obj) {
 15         complex temp;
 16         temp.r = r + obj.r;
 17         temp.v = v + obj.v;
 18         return temp;
 19     }
 20     complex operator - (complex& obj) {
 21         complex temp;
 22         temp.r = r - obj.r;
 23         temp.v= v - obj.v;
 24         return temp;
 25     }
 26     complex operator * ( complex& obj) {
 27         complex temp;
 28         temp.r = r*obj.r - v*obj.v;
 29         temp.v = r*obj.v + v*obj.r;
 30         return temp;
 31     }
 32 } p1[MAX], p2[MAX], omiga[MAX], result1[MAX], result2[MAX];
 33 void caculate_permutation(int s, int interval, int w, int next) {
 34     if(interval==n) {
 35         permutation[w] = s;
 36         return ;
 37     }
 38     caculate_permutation(s,interval*2, w, next/2);
 39     caculate_permutation(s+interval, interval*2, w+next, next/2);
 40 }
 41 void fft(complex transform[], complex p[]) {
 42     int i, j, l, num, m;
 43     complex temp1, temp2;
 44     for(i=0; i<n; i++)transform[i] = p[ permutation[i] ] ;
 45     num = 1, m = n;
 46     for(i=1; i<=k; i++) {
 47         for(j=0; j<n; j+=num*2)
 48             for(l=0; l<num; l++)
 49                 temp2 = omiga[m*l]*transform[j+l+num],
 50                         temp1 = transform[j+l],
 51                                 transform[j+l] = temp1 + temp2,
 52                                                  transform[j+l+num] = temp1 - temp2;
 53         num*=2,m/=2;
 54     }
 55 }
 56 void polynomial_by(int n1,int n2) {//多项式乘法，cof1、cof2保存的是a[0],a[1]..a[n-1]的值（a[i]*x^i）
 57     int i;
 58     double angle;
 59     k = 0, n = 1;
 60     while(n<n1+n2-1)k++,n*=2;
 61     for(i=0; i<n1; i++)p1[i].r = cof1[i], p1[i].v = 0;
 62     while(i<n)p1[i].r = p1[i].v = 0, i++;
 63     for(i=0; i<n2; i++)p2[i].r = cof2[i], p2[i].v = 0;
 64     while(i<n)p2[i].r = p2[i].v = 0, i++;
 65     caculate_permutation(0,1,0,n/2);
 66     angle = PI/n;
 67     for(i=0; i<n; i++)omiga[i].r = cos(angle*i), omiga[i].v = sin(angle*i);
 68     fft(result1,p1);
 69     fft(result2,p2);
 70     for(i=0; i<n; i++)result1[i]= result1[i]*result2[i];
 71     for(i=0; i<n; i++)omiga[i].v = -omiga[i].v;
 72     fft(result2, result1);
 73     for(i=0; i<n; i++)result2[i].r/=n;
 74     i = n -1;
 75     while(i&&fabs(result2[i].r)<eps)i--;
 76     n = i+1;
 77     while(i>=0) ans[i]=(int)(result2[i].r+0.5), i--;
 78 }
 79 int main() {
 80     while(scanf("%s",s1)!=EOF){
 81         scanf("%s",s2);
 82         int n1=strlen(s1),n2=strlen(s2);
 83         for(int i=0;i<n1;i++){
 84             cof1[i]=s1[n1-1-i]-'0';
 85         }
 86         for(int i=0;i<n2;i++){
 87             cof2[i]=s2[n2-1-i]-'0';
 88         }
 89         memset(ans,0,sizeof(ans));
 90         polynomial_by(n1,n2);
 91         for(int i=0;i<n;i++){
 92             if(ans[i]>=10){
 93                 ans[i+1]+=ans[i]/10;
 94                 ans[i]%=10;
 95             }
 96         }
 97         while(ans[n]>0){
 98             if(ans[n]>=10){
 99                 ans[n+1]+=ans[n]/10;
100                 ans[n]%=10;
101             }
102             n++;
103         }
104         for(int i=n-1;i>=0;i--){
105             putchar('0'+ans[i]);
106         }
107         puts("");
108     }
109     return 0;
110 }