hdu 1402 A * B Problem Plus(FFT)

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 const double pi=acos(-1.0);
 6 //n 必须为 2 的幂。
 7 struct comp{
 8     double r,i;
 9     comp(double _r=0,double _i=0){r=_r,i=_i;}
10     comp operator+(const comp x){return comp(r+x.r,i+x.i);}
11     comp operator-(const comp x){return comp(r-x.r,i-x.i);}
12     comp operator*(const comp x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}
13 };
14 
15 void FFT(comp a[],int n,int t){
16     for(int i=1,j=0;i<n-1;i++)
17     {
18         for(int s=n;j^=s>>=1,~j&s;);
19         if(i<j)swap(a[i],a[j]);
20     }
21     for(int d=0;(1<<d)<n;d++)
22     {
23         int m=1<<d,m2=m<<1;
24         double o=pi/m*t;comp _w(cos(o),sin(o));
25         for(int i=0;i<n;i+=m2)
26         {
27             comp w(1,0);
28             for(int j=0;j<m;j++)
29             {
30                 comp &A=a[i+j+m],&B=a[i+j],t=w*A;
31                 A=B-t,B=B+t,w=w*_w;
32             }
33         }
34     }
35     if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;
36 }
37 
38 const int N=2e5+7;
39 
40 comp x1[N],x2[N];
41 char a[N],b[N];
42 int sum[N];
43 
44 int main()
45 {
46     while(~scanf("%s%s",a,b))
47     {
48         int lena=strlen(a),lenb=strlen(b);
49         int n=1;
50         while(n<lena*2||n<lenb*2)n<<=1;
51         F(i,0,n-1)
52         {
53             if(i<lena)x1[i]=comp(a[lena-1-i]-'0',0);
54             else x1[i]=comp(0,0);
55         }
56         F(i,0,n-1)
57         {
58             if(i<lenb)x2[i]=comp(b[lenb-1-i]-'0',0);
59             else x2[i]=comp(0,0);
60         }
61         FFT(x1,n,1),FFT(x2,n,1);
62         F(i,0,n-1)x1[i]=x1[i]*x2[i];
63         FFT(x1,n,-1);
64         F(i,0,n-1)sum[i]=(int)(x1[i].r+0.5);
65         F(i,0,n-1)
66         {
67             sum[i+1]+=sum[i]/10;
68             sum[i]%=10;
69         }
70         n--;
71         while(sum[n]<=0&&n>0)n--;
72         for(int i=n;i>=0;i--)printf("%c",sum[i]+'0');
73         puts("");
74     }
75     return 0;
76 }