HDU1402（fft）

A * B Problem Plus

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

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

 1 //2017-09-07
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <complex>
 7 #include <cmath>
 8 #define Complex complex<double>
 9 
10 using namespace std;
11 
12 const double PI = acos(-1.0);
13 const int N = 110000;
14 
15 void fft(Complex y[], int n, int op){
16     for(int i = 1, j = n/2; i < n-1; i++){
17         if(i<j)swap(y[i], y[j]);
18         int k = n/2;
19         while(j >= k){
20             j -= k;
21             k /= 2;
22         }
23         if(j<k)j += k;
24     }
25     for(int h = 2; h <= n; h <<= 1){
26         Complex wn(cos(-op*2*PI/h), sin(-op*2*PI/h));
27         for(int j = 0; j < n; j += h){
28             Complex w(1, 0);
29             for(int k = j; k < j+h/2; k++){
30                 Complex u = y[k];
31                 Complex t = w*y[k+h/2];
32                 y[k] = u+t;
33                 y[k+h/2] = u-t;
34                 w = w*wn;
35             }
36         }
37     }
38 }
39 
40 char a[N], b[N];
41 Complex A[N<<1], B[N<<1];
42 int ans[N<<1];
43 void poly_muilt(){
44     int n = 1, len1 = strlen(a), len2 = strlen(b);
45     while(n<len1*2 || n<len2*2)n<<=1;
46     for(int i = 0; i < len1; i++)A[i] = a[len1-i-1]-'0';
47     for(int i = len1; i < n; i++)A[i] = 0;
48     for(int i = 0; i < len2; i++)B[i] = b[len2-i-1]-'0';
49     for(int i = len2; i < n; i++)B[i] = 0;
50     fft(A, n, 1);
51     fft(B, n, 1);
52     for(int i = 0; i < n; i++)
53           A[i] *= B[i];
54     fft(A, n, -1);
55     for(int i = 0; i < n; i++)
56           ans[i] = (int)(A[i].real()/n+0.5);
57     for(int i = 0; i < n; i++){
58         ans[i+1] += ans[i]/10;
59         ans[i] %= 10;
60     }
61     n = len1+len2-1;
62     while(ans[n] <= 0 && n > 0)n--;
63     for(int i = n; i >= 0; i--)
64       printf("%c", ans[i]+'0');
65     printf("
");
66 }
67 
68 int main()
69 {
70     while(scanf("%s%s", a, b) != EOF){
71         poly_muilt();
72     }
73 
74     return 0;
75 }