fft-fast.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <time.h>
#include <vector>
#include <list>
#include <cassert>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <cstdio>
#include <cmath>
#include <memory>
using namespace std;

typedef long long li;

#define all(a) a.begin(), a.end()
#define mp make_pair

template <typename T>
class myComplex {
private:
	T x, y;
public:
	myComplex() {}
	myComplex(T x, T y) :x(x), y(y) {}
	myComplex(T x) :x(x), y(0) {}
	T getReal() {
		return x;
	}
	T getImag() {
		return y;
	}
	T getSqrDist() {
		return x * x + y * y;
	}
	double getDist() {
		return sqrt(1.0 * getSqrDist());
	}
	myComplex operator + (const myComplex& other) const { return myComplex(x + other.x, y + other.y); }
	myComplex operator - () { return myComplex(-x, -y); }
	myComplex operator - (const myComplex& other) const { return myComplex(x - other.x, y - other.y); }
	myComplex operator * (T number) { return myComplex(x * number, y * number); }
	myComplex operator / (T number) { return myComplex(x / number, y / number); }
	myComplex operator * (const myComplex& other) const { return myComplex(x * other.x - y * other.y, x * other.y + y * other.x); }
	void print() const {
		cout << x;
		if (y > 0)
			cout << "+";
		if (y != 0)
			cout << y << "i";
		cout << "\n";
	}

};

#define double long double

typedef myComplex<double> complex;

double PI = acos((double)-1.0);

void fft(vector<complex> & a, bool invert) {
	int n = (int)a.size();

	for (int i = 1, j = 0; i < n; ++i) {
		int bit = n >> 1;
		for (; j >= bit; bit >>= 1)
			j -= bit;
		j += bit;
		if (i < j)
			swap(a[i], a[j]);
	}

	for (int len = 2; len <= n; len <<= 1) {
		double ang = 2 * PI / len * (invert ? -1 : 1);
		complex wlen(cos(ang), sin(ang));
		for (int i = 0; i < n; i += len) {
			complex w(1);
			for (int j = 0; j < len / 2; ++j) {
				complex u = a[i + j], v = a[i + j + len / 2] * w;
				a[i + j] = u + v;
				a[i + j + len / 2] = u - v;
				w = w * wlen;
			}
		}
	}
	if (invert)
		for (int i = 0; i<n; ++i)
			a[i] = a[i] / n;
}

void fft1(vector<complex>& input, bool invert) {
	int curSize = input.size();
	if (curSize == 1)
		return;
	vector<complex> rec[2];
	for (int w = 0; w < 2; ++w)
		rec[w].resize(curSize / 2);
	for (int i = 0; i < input.size(); i += 2) {
		rec[0][i / 2] = input[i];
		rec[1][i / 2] = input[i + 1];
	}

	for (int w = 0; w < 2; ++w)
		fft1(rec[w], invert);

	double alpha = 2 * acos(-1.0) / curSize * (invert ? -1 : 1);
	complex wn = complex(cos(alpha), sin(alpha));
	complex w = 1;

	for (int i = 0; i < curSize / 2; ++i) {
		input[i] = rec[0][i] + w * rec[1][i];
		input[i + curSize / 2] = rec[0][i] - w * rec[1][i];
		if (invert) {
			input[i] = input[i] / 2;
			input[i + curSize / 2] = input[i + curSize / 2] / 2;
		}
		w = w * wn;
	}

}

vector <double> multiply(const vector<double>& a, const vector<double>& b) {
	int n = 1;
	while (n <= a.size() || n <= b.size())
		n <<= 1;
	n <<= 1;
	vector<complex> input[2];
	for (int w = 0; w < 2; ++w)
		input[w].assign(n, complex(0, 0));
	for (int i = 0; i < a.size(); ++i)
		input[0][i] = a[i];
	for (int i = 0; i < b.size(); ++i)
		input[1][i] = b[i];
	for (int w = 0; w < 2; ++w) {
		fft(input[w], false);
	}
	vector <complex> res(n);
	for (int i = 0; i < n; ++i)
		res[i] = input[0][i] * input[1][i];
	fft(res, true);
	vector<double> answer;
	for (int i = 0; i < n; ++i)
		answer.push_back(res[i].getReal());
	return answer;
}

vector <double> naive(vector<double> a, vector<double> b) {
	vector<double> res(a.size() + b.size() - 1);
	for (int i = 0; i < a.size(); ++i)
		for (int j = 0; j < b.size(); ++j)
			res[i + j] += a[i] * b[j];
	return res;
}

int MAGIC = 3;
int base = 1000;


int main() {
#ifdef PROGA
	freopen("in.txt", "r", stdin);
#endif

	int t;
	cin >> t;
	while (t--) {

		vector<double> a[2];
		for (int w = 0; w < 2; ++w) {
			string s;
			cin >> s;
			reverse(all(s));
			for (int i = 0;; i += MAGIC) {
				int cur = 0;
				for (int w = min(i + MAGIC, (int)s.length()) - 1; w >= i; --w)
					cur = cur * 10 + (int)(s[w] - '0');
				a[w].push_back(cur);
				if (i + MAGIC >= s.length())
					break;
			}
		}
		vector<double> resFFT = multiply(a[0], a[1]);
		vector <long long> res;
		for (int i = 0; i < resFFT.size(); ++i)
			res.push_back(resFFT[i] + 0.5);

		/*for (int i = 0; i < res.size(); ++i)
			cout << res[i] << ' ';
			cout << endl;*/

		for (int i = 0; i + 1 < res.size(); ++i) {
			res[i + 1] += res[i] / base;
			res[i] %= base;
		}

		bool flag = false;
		int first = -1;
		for (int i = res.size() - 1; i >= 0; --i) {
			if (res[i] != 0) {
				flag = true;
				if (first == -1)
					first = i;
			}
			if (flag) {
				if (i != first) {
					for (int w = base / 10; w > 1; w /= 10)
						if (res[i] < w)
							printf("0");
				}
				printf("%d", res[i]);
			}
		}
		if (!flag)
			printf("0");
		printf("\n");

	}

}