1 // fft模板 HDU 1402  2   3 #include <iostream>  4 #include <cstdio>  5 #include <cstdlib>  6 #include <algorithm>  7 #include <vector>  8 #include <math.h>  9 #include <memory.h> 10 #include <bits/stdc++.h> 11 using namespace std; 12 #define LL long long 13 typedef pair<int,int> pii; 14 const LL inf = 0x3f3f3f3f; 15 const LL MOD =100000000LL; 16 const int N = 150010; 17 const double eps = 1e-8; 18 void fre() {freopen("in.txt","r",stdin);} 19 void freout() {freopen("out.txt","w",stdout);} 20 inline int read() {int x=0,f=1;char ch=getchar();while(ch>‘9‘||ch<‘0‘) {if(ch==‘-‘) f=-1; ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}return x*f;} 21  22  23 const double PI = acos(-1.0); 24 //复数结构体 25 struct Complex{ 26     double r,i; 27     Complex(double _r = 0.0,double _i = 0.0){ 28         r = _r; i = _i; 29     } 30     Complex operator +(const Complex &b){ 31         return Complex(r+b.r,i+b.i); 32     } 33     Complex operator -(const Complex &b){ 34         return Complex(r-b.r,i-b.i); 35     } 36     Complex operator *(const Complex &b){ 37         return Complex(r*b.r-i*b.i,r*b.i+i*b.r); 38     } 39 }; 40 /* 41  * 进行FFT和IFFT前的反转变换。 42  * 位置i和 （i二进制反转后位置）互换 43  * len必须去2的幂 44  */ 45 void change(Complex y[],int len){ 46     int i,j,k; 47     for(i = 1, j = len/2;i < len-1; i++){ 48         if(i < j)swap(y[i],y[j]); 49         //交换互为小标反转的元素，i<j保证交换一次 50         //i做正常的+1，j左反转类型的+1,始终保持i和j是反转的 51         k = len/2; 52         while( j >= k){ 53             j -= k; 54             k /= 2; 55         } 56         if(j < k) j += k; 57     } 58 } 59 /* 60  * 做FFT 61  * len必须为2^k形式， 62  * on==1时是DFT，on==-1时是IDFT 63  */ 64 void fft(Complex y[],int len,int on){ 65     change(y,len); 66     for(int h = 2; h <= len; h <<= 1){ 67         Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h)); 68         for(int j = 0;j < len;j+=h){ 69             Complex w(1,0); 70             for(int k = j;k < j+h/2;k++){ 71                 Complex u = y[k]; 72                 Complex t = w*y[k+h/2]; 73                 y[k] = u+t; 74                 y[k+h/2] = u-t; 75                 w = w*wn; 76             } 77         } 78     } 79     if(on == -1) 80         for(int i = 0;i < len;i++) 81             y[i].r /= len; 82 } 83  84 Complex a[N],b[N]; 85 char s1[N/2],s2[N/2]; 86 int ans[N]; 87 int main(){ 88     while(~scanf("%s%s",s1,s2)){ 89          int len1=strlen(s1); 90          int len2=strlen(s2); 91          int l1=0,l2=0; 92          while((1<<l1)<len1) l1++; 93          while((1<<l2)<len2) l2++; 94          int len=(1<<(max(l1,l2)+1)); 95          for(int i=0;i<len;i++){ 96             if(i<len1) a[i]=Complex(s1[len1-i-1]-‘0‘,0); 97             else a[i]=Complex(0,0); 98             if(i<len2) b[i]=Complex(s2[len2-i-1]-‘0‘,0); 99             else b[i]=Complex(0,0);  100          }101          fft(a,len,1);102          fft(b,len,1);103          for(int i=0;i<len;i++)104             a[i]=a[i]*b[i];105          fft(a,len,-1);106          for(int i=0;i<len;i++)107             ans[i]=(int)(a[i].r+0.5);108          for(int i=0;i<len-1;i++){109             ans[i+1]+=ans[i]/10;110             ans[i]%=10;111          }112          bool flag=false;113          for(int i=len-1;i>=0;i--){114             if(ans[i]) printf("%d",ans[i]),flag=true;115             else if(flag||i==0)printf("0");116         }117         printf("\n");118     }119     return 0;120 }