记录编号	170865	评测结果	AAAAAAAEEE
题目名称	超强的乘法问题	最终得分	70
用户昵称	HouJikan	是否通过	未通过
代码语言	C++	运行时间	0.347 s
提交时间	2015-07-16 19:56:02	内存使用	7.38 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
#include <string>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;
const double PI = 3.1415926535897932384626433;
///===================struct declaration======================
struct Complexs{
	double x, y;
	#define cpx Complexs
	cpx (double x = 0, double y = 0): x(x), y(y){}
	cpx operator + (const cpx a) const{return cpx(x + a.x, y + a.y);}
	cpx operator - (const cpx a) const{return cpx(x - a.x, y - a.y);}
	cpx operator * (const cpx a) const{return cpx(x * a.x - y * a.y, x * a.y + y * a.x);}
};
///===================var declaration=========================
const int MAXN = 50050 * 4;
int len1, len2, len;
int ans[MAXN];
cpx x[MAXN], y[MAXN];
char ch[MAXN];
///===================function declaration====================
bool Init();
void Rader_Transform(cpx *X);
void FFT(cpx *X, int mode);
void Print();
///===================main code===============================
int main(){
#ifndef ONLINE_JUDGE
	 freopen("bettermul.in","r",stdin);
	 freopen("bettermul.out","w",stdout);
#endif
	 while (Init()){
		 FFT(x, 1);
		 FFT(y, 1);
		 for(int i = 0; i < len; i ++)
			 x[i] = x[i] * y[i];
		 FFT(x, -1);
		 Print();
	 }
	 return 0;
}
///==================function code===========================
bool Init(){
	if (scanf("%s", ch) == EOF) return false;
	len1 = strlen(ch);
	for(int i = 0; i < len1; i ++)
		x[len1 - i - 1].x = ch[i] - '0';
	scanf("%s", ch);
	len2 = strlen(ch);
	for(int i = 0; i < len2; i ++)
		y[len2 - i - 1] = ch[i] - '0';
	len = 1;
	while (len < len1 * 2 || len < len2 * 2)
		len = len * 2;
	for(int i = len1; i < len; i ++)
		x[i].x = x[i].y = 0;
	for(int i = len2; i < len; i ++)
		y[i].x = y[i].y = 0;
	return true;
}
void Rader_Transform(cpx *X){
	for(int i = 1, j = len >> 1; i < len - 1; i ++){
		if (i < j)
			swap(X[i], X[j]);
		int k = len >> 1;
		while (j >= k){
			j -= k;
			k = k >> 1;
		}
		if (j < k)
			j += k;
	}
}
void FFT(cpx *X, int mode){
	Rader_Transform(X);
	for(int d = 2; d <= len; d = d * 2){
		cpx Wn = cpx(cos(2 * PI / d * mode), sin(2 * PI / d * mode));
		for(int j = 0; j < len; j += d){
			cpx W = cpx(1, 0);
			for(int k = j; k < j + d / 2; k ++){
				cpx O_K = X[k], E_K = W * X[k + d / 2];
				X[k] = O_K + E_K;
				X[k + d / 2] = O_K - E_K;
				W = W * Wn;
			}
		}
	}
	if (mode == -1)
		for(int i = 0; i < len; i ++)
			X[i].x = X[i].x / len;
}
void Print(){
	memset(ans, 0, sizeof(ans));
	for(int i = 0; i < len; i ++)
		ans[i] = int(x[i].x + 0.5);
	for(int i = 0; i < len; i ++)
		ans[i + 1] += ans[i] / 10, ans[i] %= 10;
	while (ans[len] == 0 && len)
		len --;
	for(int i = len; i >= 0; i --)
		putchar(ans[i] + '0');
	putchar('\n');
}