代码

# include <cstdio>
# include <cstring>
# include <cmath>
# include <algorithm>

using namespace std;

namespace fft
{
	typedef long long ll;
	
	struct cp
	{
		double a, b;
		cp operator +(const cp &o) { return {a + o.a , b + o.b}; }
		cp operator -(const cp &o) { return {a - o.a , b - o.b}; }
		cp operator *(const cp &o) { return {a * o.a - b * o.b , a * o.b + b * o.a}; }
		cp operator *(const double &o) { return {a * o , b * o}; }
		cp operator !() { return {a , -b}; }
	};
	
	const double pai = acos(-1);
	const int MAX_N = 1 << 21;
	
	cp w[MAX_N];
	cp x[MAX_N], y[MAX_N], z[MAX_N];
	int pos[MAX_N];
	
	void init(int n)
	{
		int x = 0;
		while((1 << x) < n)
			x++;
		x--;
		int i;
		for(i = 0 ; i < n ; i++)
			pos[i] = pos[i >> 1] >> 1 | ((i & 1) << x);
	}
	
	void fft(cp * x , int n , int sta)
	{
		int i, j, k;
		for(i = 0 ; i < n ; i++)
			if(i < pos[i])
				swap(x[i] , x[pos[i]]);
				
		w[0] = {1 , 0};
		
		for(i = 2 ; i <= n ; i <<= 1)
		{
			cp g = {cos(2 * pai / i) , sin(2 * pai / i) * sta};
			int fro = i >> 1;
			for(j = fro ; j >= 0 ; j -= 2)
				w[j] = w[j >> 1];
			for(j = 1 ; j < fro ; j += 2)
				w[j] = w[j - 1] * g;
			for(j = 0 ; j < n ; j += i)
			{
				cp * a = x + j, * b = a + fro;
				for(k = 0 ; k < fro ; k++)
				{
					cp o = b[k] * w[k];
					b[k] = a[k] - o;
					a[k] = a[k] + o;
				}
			}
			
		}
		
		if(sta == -1)
		{
			for(i = 0 ; i < n ; i++)
			{
				x[i].a /= n;
				x[i].b /= n;
			}
		}
	}
	
	void FFT(int * a , int n , int * b , int m , ll * c)
	{
		int len = 2;
		while(len < (n + m + 1))
			len <<= 1;
		len >>= 1;
		
		init(len);
		
		memset(x + n / 2 , 0 , sizeof(cp) * (len - n / 2));
		memset(y + m / 2 , 0 , sizeof(cp) * (len - m / 2));
		
		int i;
		for(i = 0 ; i < n ; i++)
			(i & 1 ? x[i >> 1].b : x[i >> 1].a) = a[i];
		for(i = 0 ; i < m ; i++)
			(i & 1 ? y[i >> 1].b : y[i >> 1].a) = b[i]; 
		
		fft(x , len , 1);
		fft(y , len , 1);

		int siz = len >> 1;
		for(i = 0 ; i < siz ; i++)
		{
			int j = len - 1 & len - i;
			z[i] = x[i] * y[i] - (x[i] - !x[j]) * (y[i] - !y[j]) * ((cp){1 , 0} + w[i]) * 0.25;
		}
		
		for(i = siz ; i < len ; i++)
		{
			int j = len - 1 & len - i;
			z[i] = x[i] * y[i] - (x[i] - !x[j]) * (y[i] - !y[j]) * ((cp){1 , 0} - w[i ^ len >> 1]) * 0.25;
		}

		fft(z , len , -1);
		
		siz = n + m;
		for(i = 0 ; i < siz ; i++)
			c[i] = (ll)((i & 1 ? z[i >> 1].b : z[i >> 1].a) + 0.5);
	}
	
	ll sum[MAX_N];
	int x1[MAX_N], x2[MAX_N];
	void mul(char * a , char * b , char * ans)
	{
		int la = strlen(a), lb = strlen(b);
		 
		int i;
		for(i = la - 1 ; i >= 0 ; i--)
			x1[la - 1 - i] = a[i] - 48;
		
		for(i = lb - 1 ; i >= 0 ; i--)
			x2[lb - 1 - i] = b[i] - 48;
		
		FFT(x1 , la , x2 , lb , sum);
		int l = la + lb;
		sum[l] = 0;
		
		for(i = 0 ; i < l ; i++)
		{
			sum[i + 1] += sum[i] / 10;
			sum[i] %= 10;
		}
			
		while(!sum[l] && l)
			l--;
			
		for(i = l ; i >= 0 ; i--)
			ans[l - i] = sum[i] + 48;
		ans[l + 1] = 0;
	}
}

using fft::mul;
using fft::MAX_N; 

char a[MAX_N];
char b[MAX_N];
char ans[MAX_N];

int main()
{
	scanf("%s %s", a, b);
	
	mul(a , b , ans);
	
	puts(ans);
	
	return 0;
} 

评测结果