A * B Problem Plus

题目连接：

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

Hint

题意

题解：

考虑变成系数的形式，显然就是两个的多项式乘法

然后转化成FFT，直接莽一波就完了。

代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int N = 500005;const double pi = acos(-1.0);char s1[N],s2[N];int len,res[N];struct Complex{    double r,i;    Complex(double r=0,double i=0):r(r),i(i) {};    Complex operator+(const Complex &rhs)    {        return Complex(r + rhs.r,i + rhs.i);    }    Complex operator-(const Complex &rhs)    {        return Complex(r - rhs.r,i - rhs.i);    }    Complex operator*(const Complex &rhs)    {        return Complex(r*rhs.r - i*rhs.i,i*rhs.r + r*rhs.i);    }} va[N],vb[N];void rader(Complex F[],int len) //len = 2^M,reverse F[i] with  F[j] j为i二进制反转{    int j = len >> 1;    for(int i = 1;i < len - 1;++i)    {        if(i < j) swap(F[i],F[j]);  // reverse        int k = len>>1;        while(j>=k)        {            j -= k;            k >>= 1;        }        if(j < k) j += k;    }}void FFT(Complex F[],int len,int t){    rader(F,len);    for(int h=2;h<=len;h<<=1)    {        Complex wn(cos(-t*2*pi/h),sin(-t*2*pi/h));        for(int j=0;j
        
         =0;--i)    {        if(res[i])        {            high = i;            break;        }    }    for(int i=high;i>=0;--i) putchar('0'+res[i]);    puts("");}int main(){    while(scanf("%s %s",s1,s2)==2)    {        init(s1,s2);        gao();    }    return 0;}