记录编号	397101	评测结果	AAAAAAAAAA
题目名称	超强的乘法问题	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.774 s
提交时间	2017-04-19 18:15:11	内存使用	43.80 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 6e5 + 10;
const double PI = acos(-1.0);

struct Complex {
	double real, imag;
	Complex() {}
	Complex(double r, double i) { real = r, imag = i; }
	
	Complex operator +(const Complex &b) { return Complex(real + b.real, imag + b.imag); }
	Complex operator -(const Complex &b) { return Complex(real - b.real, imag - b.imag); }
	Complex operator *(const Complex &b) { 
		return Complex(real * b.real - imag * b.imag, real * b.imag + imag * b.real);
	} 
} ;

class FastFourierTransform {
private:
	int bit_num, fft_len;
	Complex cala[MAXN], calb[MAXN], calc[MAXN], swap_tmp[MAXN];
	
	int bit_rev(int tar) {
		int res = 0, len = bit_num;
		while (len--) res |= (tar & 1) << len, tar >>= 1;
		return res;
	} 
	
	inline void fill(int *tar, Complex *res, int len) {
		int now = 0;
		for (; now <= len; now++) res[now] = Complex(tar[now + 1], 0);
		while (now < fft_len) res[now++] = Complex(0, 0);
	}
	
	inline void fft(Complex *tar, Complex *res, int flag = 1) {
		for (int i = 0; i < fft_len; i++) res[i] = tar[bit_rev(i)];
		
		Complex wn, w, u, v;
		for (int d = 2; d <= fft_len; d <<= 1) {
			wn = Complex(cos(2.0 * PI / d), flag * sin(2.0 * PI / d));
			int mid = d >> 1;
			
			for (int i = 0; i < fft_len; i += d) {
				Complex w = Complex(1, 0);
				for (int j = 0; j < mid; j++) {
					u = res[i + j], v = w * res[i + j + mid];
					
					res[i + j] = u + v;
					res[i + j + mid] = u - v;
					w = w * wn; 
				}
			}
		}
		
		if (flag == -1) for (int i = 0; i < fft_len; i++) res[i].real /= fft_len;
	}
	
public:
	inline void solve(int lena, int *tara, int lenb, int *tarb, int *ans, int &ans_len) {
		fft_len = 1, bit_num = 0;
		int tmp = max(lena, lenb) << 1;
		while (fft_len < tmp) fft_len <<= 1, bit_num++;
		
		fill(tara, swap_tmp, lena);
		fft(swap_tmp, cala);
		
		fill(tarb, swap_tmp, lenb);
		fft(swap_tmp, calb);
		
		for (int i = 0; i < fft_len; i++) swap_tmp[i] = cala[i] * calb[i];
		fft(swap_tmp, calc, -1);
		
		for (int i = 0; i < fft_len; i++) ans[i + 1] = calc[i].real + 0.5;
		ans_len = fft_len;
	}
} FFT;

int numa[MAXN], lena;
int numb[MAXN], lenb;
int numc[MAXN], lenc;

#define is_num(x) (x <= '9' and x >= '0')
inline int get_line(int *tar) {
	char tmp = getchar();
	int i = 0;
	
	while (not is_num(tmp)) tmp = getchar();
	while (    is_num(tmp)) {
		tar[++i] = tmp - '0';
		tmp = getchar();
	}
	
	return i;
}

inline void read() {
	lena = get_line(numa);
	lenb = get_line(numb);
}

inline void solve() {
	for (int i = 1; i <= (lena >> 1); i++) swap(numa[i], numa[lena - i + 1]);
	for (int i = 1; i <= (lenb >> 1); i++) swap(numb[i], numb[lenb - i + 1]);
	FFT.solve(lena, numa, lenb, numb, numc, lenc);
	
	int tmp = 0;
	for (int i = 1; i <= lenc; i++) {
		numc[i] += tmp;
		tmp = numc[i] / 10;
		numc[i] %= 10;
	}
	
	bool zero = false;
	for (int i = lenc; i>= 1; i--) {
		if ((not zero) and (not numc[i])) continue;
		zero = true;
		printf("%d", numc[i]);
	}
}

int main() {
	freopen("bettermul.in", "r", stdin);
	freopen("bettermul.out", "w", stdout);
	read();
	solve();
	return 0;
}