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

1210002

Sample Output

22000

题解

---

做卷积主要思想是，先把系数表达式转化为点值表达式，而点值表达式相乘的时间复杂度是\(O(n)\)的，唯一需要优化的是这个转化的过程，需要使用fft进行优化，时间负责度可以降为\(O(nlogn)\)，具体算法思想参看

资料：

参考代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define ll long long#define inf 1000000000#define PI acos(-1)#define mem(a,x) memset(a,x,sizeof(a))using namespace std;ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}void Out(ll a){ if(a<0) putchar('-'),a=-a; if(a>=10) Out(a/10); putchar(a%10+'0');}const int N=200005;typedef complex
            
              E;E a[N],b[N],A[N],c[N];char s1[N],s2[N];int sum[N],a1[N],a2[N],dig[N],rev[N];void FFT(E a[],int n,int flag){ E x,y; for(int i=0;i
             
              >=1) dig[len++]=t&1; for(int j=0;j
              
               0)l--; for(int i=l;i>=0;i--) putchar(sum[i]+'0'); putchar('\n'); } return 0;}