代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,x,y) for(int i = x;i <= y;i++)
#define fd(i,x,y) for(int i = x;i >= y;i--)
#define p 4179340454199820289ll
#define m 1000000
#define bi 2100010
#define bs 4000010
using namespace std;
typedef long long  ll;
ll a[bi],b[bi],w[bi >> 1];
int len,tp,N,lg;
char s[bs],stk[10],buf[10000010];
int B = -1;
#define gc() buf[++B]
ll ksc(ll x,ll y)
{
	ll a = (ll)((1.0L * x * y) / (1.0L * p)),b = x * y - a * p;
	b -= p;
	while(b < 0) b += p;
	return b;
}
ll ksm(ll x,ll y)
{
	ll res = 1;
	while(y > 0)
	{
		if(y & 1) res = ksc(res,x);
		x = ksc(x,x),y >>= 1;
	}
	return res;
}
#define add(x,y) (x + y >= p ? x + y - p : x + y)
#define sub(x,y) (x < y ? x - y + p : x - y)
void DIF(ll *a)
{
	for(int l = N >> 1;l;l >>= 1)
	{
		ll *r = w;
		for(int i = 0;i < N;i += l << 1)
		{
			fo(j,0,l - 1)
			{
				ll x = a[i + j + 1],y = ksc(a[i + j + l + 1],*r);
				a[i + j + 1] = add(x,y),a[i + j + l + 1] = sub(x,y);
			}
			++r;
		}
	}
}
void DIT(ll *a)
{
	for(int l = 1;l < N;l <<= 1)
	{
		ll *r = w;
		for(int i = 0;i < N;i += (l << 1))
		{
			fo(j,0,l - 1)
			{
				ll x = a[i + j + 1],y = a[i + j + l + 1];
				a[i + j + 1] = add(x,y),a[i + j + l + 1] = ksc(sub(x,y),*r);
			}
			++r;
		}
	}
	fo(i,1,N - 1 >> 1) a[i + 1] ^= a[N - i + 1] ^= a[i + 1] ^= a[N - i + 1];
	ll ny = ksm(N,p - 2);
	fo(i,1,N) a[i] = ksc(a[i],ny);
}
void NTT(ll *a,int xs) {xs == 1 ? DIF(a) : DIT(a);}
void clr(ll *A) {fd(i,A[0],0) A[i] = 0;}
void cpy(ll *A,ll *B) {clr(A);fo(i,0,B[0]) A[i] = B[i];}
void rd(ll *a)
{
	char ch = gc();
	while(ch < 48 || ch > 57) ch = gc();
	len = -1;
	while(ch >= 48 && ch <= 57) s[++len] = ch,ch = gc();
	tp = -1;
	fd(i,len,0)
	{
		stk[++tp] = s[i];
		if(tp == 5)
		{
			a[0]++;
			fd(j,tp,0) a[a[0]] = a[a[0]] * 10 + stk[j] - 48;
			tp = -1;
		}
	}
	if(tp != -1)
	{
		a[0]++;
		fd(j,tp,0) a[a[0]] = a[a[0]] * 10 + stk[j] - 48;
		tp = -1;
	}
}
void print(int x)
{
	if(x < 0) putchar('-'),x = -x;
	char ch[20];
	int w = -1;
	if(x == 0) ch[++w] = 48;
	while(x) ch[++w] = x % 10 + 48,x /= 10;
	fd(i,w,0) putchar(ch[i]);
}
void printL(ll *a)
{
	print(a[a[0]]);
	fd(i,a[0] - 1,1)
	{
		ll t = a[i];
		int w = (t == 0);
		while(t) t /= 10,w++;
		fo(j,0,5 - w) putchar(48);
		print(a[i]);
	}
}
int main()
{
	fread(buf,1,10000000,stdin);
	rd(a),rd(b),N = 1,lg = 0;
	while(N <= a[0] + b[0]) N <<= 1,lg++;
	w[0] = 1,w[1 << lg - 1] = ksm(3,p - 1 >> lg + 1);
	fd(i,lg - 1,1) w[1 << i - 1] = ksc(w[1 << i],w[1 << i]);
	fo(i,1,1 << lg - 1) w[i] = ksc(w[i & i - 1],w[i & -i]);
	NTT(a,1),NTT(b,1);
	fo(i,1,N) a[i] = ksc(a[i],b[i]);
	NTT(a,-1);
	a[0] = N + 10;
	fo(i,1,N + 10) a[i + 1] += a[i] / m,a[i] %= m;
	while(a[a[0]] == 0 && a[0] > 0) a[0]--;
	printL(a);
	return 0;
}

评测结果