A * B Problem Plus

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 16111    Accepted Submission(s): 3261

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

 

 

Recommend

 

 

题意：求高精度a*b                                  --代码参考kuangbin大神

思路： 

通过FFT我们可以快速求出多项式的卷积，从而解决数相乘。                 

求卷积大致如下图，至于FFT具体原理看不太懂- -

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;typedef long double ld;const ld eps=1e-10;const int inf = 0x3f3f3f;const int MOD = 1e9+7;const double PI = acos(-1.0);struct Complex{ double x,y; Complex(double _x = 0.0,double _y = 0.0) { x = _x; y = _y; } Complex operator-(const Complex &b)const { return Complex(x-b.x,y-b.y); } Complex operator+(const Complex &b)const { return Complex(x+b.x,y+b.y); } Complex operator*(const Complex &b)const { return Complex(x*b.x-y*b.y,x*b.y+y*b.x); }};void change(Complex y[],int len){ int i,j,k; for(i = 1,j = len/2; i < len-1; i++) { if(i < j) swap(y[i],y[j]); k = len/2; while(j >= k) { j-=k; k/=2; } if(j < k) j+=k; }}void fft(Complex y[],int len,int on){ change(y,len); for(int h = 2; h <= len; h <<= 1) { Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h)); for(int j = 0; j < len; j+=h) { Complex w(1,0); for(int k = j; k < j+h/2; k++) { Complex u = y[k]; Complex t = w*y[k+h/2]; y[k] = u+ t; y[k+h/2] = u-t; w = w*wn; } } } if(on == -1) { for(int i = 0; i < len; i++) y[i].x /= len; }}const int maxn = 200100;Complex x1[maxn],x2[maxn];char str1[maxn],str2[maxn];int sum[maxn];int main(){ while(scanf("%s%s",str1,str2) != EOF) { int len1 = strlen(str1); int len2 = strlen(str2); int len = 1; while(len < len1*2 || len < len2*2) len <<= 1; for(int i = 0; i < len1; i++) x1[i] = Complex(str1[len1-i-1]-'0',0); for(int i = len1; i < len; i++) x1[i] = Complex(0,0); for(int i = 0; i < len2; i++) x2[i] = Complex(str2[len2-1-i]-'0',0); for(int i = len2; i < len; i++) x2[i] = Complex(0,0); fft(x1,len,1); fft(x2,len,1); for(int i = 0; i < len; i++) { x1[i] =x1[i]*x2[i]; //cout << x1[i].x << " "<< x1[i].y <
           
            < len;i++){ sum[i] = (int)(x1[i].x+0.5); //cout << sum[i] << endl; } for(int i = 0; i < len; i++) { sum[i+1] += sum[i]/10; sum[i] %= 10; } len= len1+len2-1; while(sum[len] <= 0 && len > 0) len--; for(int i = len; i >= 0; i--) printf("%c",sum[i]+'0'); printf("\n"); } return 0;}