代码

// http://uoj.ac/submission/9660
// 从 UOJ 上抄代码好开心啊……

#include <stdio.h>
#include <algorithm>

#define if if (
#define then )
#define do )
#define for for (
#define while while (
#define begin {
#define end }

char ch;
inline void read(int &x)
begin
	x=0;ch=getchar();
	while ch<=32 do ch=getchar();
	while ch>32 do x=x*10+ch-48,ch=getchar();
end;

const int mo=104857601;
const int _g=3,_g_inv=34952534;

int wn[2][30];

inline int qpow(int a,int b,int p)
begin
	while p do begin
		if p&1 then a=1LL*a*b%mo;
		b=1LL*b*b%mo;
		p>>=1;
	end;
	return a;
end;

inline int getinv(int x)
begin
	return qpow(1,x,mo-2);
end;

inline void FFT_init()
begin
	int i;
	for i=1;i<=25;i++ do begin
		wn[0][i]=qpow(1,_g,(mo-1)>>i);
		wn[1][i]=qpow(1,_g_inv,(mo-1)>>i);
	end;
end;

inline int bitrev(int x,int lgN)
begin
	int ret=0;
	int i;
	for i=0;i<lgN;i++ do ret|=((x>>i)&1)<<(lgN-1-i);
	return ret;
end;

inline void FFT(int *a,int lgN,bool rev)
begin
	int i,j,k;
	int N=1<<lgN;
	for i=0;i<N;i++ do begin
		int t=bitrev(i,lgN);
		if i<t then std::swap(a[i],a[t]);
	end;
	for i=0;i<lgN;i++ do begin
		int t=1<<i;
		int ww=wn[rev][i+1];
		for j=0;j+t<N;j+=t+t do begin
			int *A=a+j;
			int w=1;
			for k=0;k<t;k++ do begin
				long long tmp=1LL*A[k+t]*w;
				A[k+t]=(A[k]-tmp)%mo;
				A[k]=(A[k]+tmp)%mo;
				w=1LL*w*ww%mo;
			end;
		end;
	end;
	for i=0;i<N;i++ do a[i]=(a[i]+mo)%mo;
	if rev then begin
		int tmp=getinv(N);
		for i=0;i<N;i++ do a[i]=1LL*a[i]*tmp%mo;
	end;
end;

#define M (1<<20)

int n,m;
int a[M*2],b[M*2];

int main()
begin
	n = m = 1000000;
	FFT_init();
	int i;
	static char buf[M];
	scanf("%s", buf);
	for i=0;i<n;i++ do a[n - 1 - i] = buf[i] - 48;
	scanf("%s", buf);
	for i=0;i<m;i++ do b[m - 1 - i] = buf[i] - 48;
	int t=1;
	while (1<<t)<n+m do ++t;
	FFT(a,t,0);FFT(b,t,0);
	for i=0;i<(1<<t);i++ do a[i]=1LL*a[i]*b[i]%mo;
	FFT(a,t,1);
	a[n + m - 1] = 0;
	for i = 0; i < n + m - 1; i++ do a[i + 1] += a[i] / 10, a[i] %= 10;
	i = n + m - 1;
	while !a[i] do --i;
	while i >= 0 do putchar(a[i] + 48), --i;
end

评测结果