2016-08-24

51nod 1028 大数乘法【FFT】

题目链接：

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1028

题意：

给出$2$个大整数$A,B$，计算$A*B$的结果。

分析：

多位数乘法过程实质就是多项式乘法的过程,
$n^2$的复杂度不行，$FFT\ O(nlogn)$优化一下即可。
hdu1402一样的题目

代码：

/*************************************************************************
    > File Name: 1402.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/24 20:39:36
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 4e5 + 5;
const double pi = acos(-1.0); 
struct complex
{
    double r, i;
    complex() {r = i = 0;}
    complex(double a,double b){r = a; i = b;}
    complex operator + (const complex &o) const{
        return complex(r + o.r, i + o.i);
    }
    complex operator - (const complex &o) const{
        return complex(r - o.r, i - o.i);
    }
    complex operator * (const complex &o) const{
        return complex(r * o.r - i * o.i, r * o.i + i * o.r);
    }
}x1[maxn], x2[maxn], A[maxn];
 
int n, rev[maxn];
double a[maxn], b[maxn];
int c[maxn];
void init(int &l, int len1, int len2)
{
	int L, k, r, t;
	k = 1; L = 0;
    while(k < 2 * len1 || k < 2 * len2) k <<= 1, ++ L;
    l = k;
    for(int i = 0; i < l; i++){
        t = i; r = 0; k = L;
        while(k--){
            r <<= 1;
            r |= t & 1; 
            t >>= 1;
        }
        rev[i] = r;
    }
}
void fft(complex *x, int l, int op)
{
    complex u, t;
    for(int i = 0; i < l; i++) A[rev[i]] = x[i];
    for(int i = 0; i < l; i++) x[i] = A[i];
    for(int k = 2; k <= l; k <<= 1){
        complex wn(cos(2 * pi/ k * op), sin(2 * pi / k * op));
        for(int i = 0; i < l; i += k){
            complex w(1, 0);
            for(int j = 0; j < k / 2; j++){
                u = x[i + j]; t = w * x[i + j + k/2];
                x[i + j] = u + t; x[i + j + k/2] = u - t;
                w = w * wn;
            }
        }
    }
	//IDFT
    for(int i = 0; i < l && op == -1; i++)  x[i].r /= l;
}
char s1[maxn], s2[maxn];
int main()
{
	while(~scanf("%s%s", s1, s2)){
		int len1 = strlen(s1), len2 = strlen(s2);
		int l; init(l, len1, len2);
		for(int i = 0; i < l; i++){
			x1[i] = complex(0, 0);
			x2[i] = complex(0, 0);
		}
		for(int i = 0; i < len1; i++) x1[i].r = s1[len1 - 1 - i] - '0';
		for(int i = 0; i < len2; i++) x2[i].r = s2[len2 - 1 - i] - '0';
	    fft(x1, l, 1); fft(x2, l, 1);
    	for(int i = 0; i < l; i++)	x1[i] = x1[i] * x2[i];	
		fft(x1, l, -1);
		memset(c, 0, sizeof(c));
	    for(int i = 0; i < l; i++){
			c[i] = x1[i].r + 0.5;
			//cout<<x1[i].r<<' '<<c[i]<<endl;
		}
		for(int i = 0; i < l; i++){
			c[i + 1] += c[i] / 10;
			c[i] %= 10;
		}
		int i = l;
		while(i && c[i] == 0) i--;
		for(int j = i; j >= 0; j-- ){
			printf("%d", c[j]);
		}
		puts("");
	}
    return 0;
}