代码

#include<bits/stdc++.h>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;i++)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;i--)
#define ll long long
#define flush()(fwrite(out,1,os-out,stdout),os=out)
#define put(x)(*os++=x,os==ot?flush():0)
#define gc()(it==is?it=(is=in)+fread(in,1,P,stdin),(it==is?EOF:*is++):*is++)
#define db double
using namespace std;
const int N=1e6+5,M=(1<<21)+1,mo=998244353,P=(1<<21)+1;
const db pi=acos(-1);
char in[P],*is=in,*it=in,out[P],*os=out,*ot=out+P-1,o[20],c;
int n,m,Q;
int h[M],aa[M];
db ny;
struct no{
	db x,y;
	no(){x=y=0;}
	no(const db &_x,const db &_y){x=_x;y=_y;}
}a[M],b[M],w[M],A;
void dft(no *a){
	fo(i,1,Q)if(i<h[i])swap(a[i],a[h[i]]);
	for(int i=2,j,m,k;m=i>>1,i<=Q;i<<=1){
		no g=no(cos(pi*2/i),sin(pi*2/i));
		w[0]=no(1,0);
		for(k=1;k<m;k++){
			w[k].x=w[k-1].x*g.x-w[k-1].y*g.y;
			w[k].y=w[k-1].x*g.y+w[k-1].y*g.x;
		}
		for(j=0;j<Q;j+=i){
			no *l=a+j,*r=a+j+m;
			for(k=0;k<m;k++){
				A.x=w[k].x*(*r).x-w[k].y*(*r).y;
				A.y=w[k].x*(*r).y+w[k].y*(*r).x;
				(*r).x=(*l).x-A.x;
				(*r).y=(*l).y-A.y;
				(*l).x+=A.x;
				(*l).y+=A.y;
				l++;r++;
			}
		}
	}
}
int main(){
	for(;(c=gc())<='9'&&c>='0';)a[++n].x=c-48;
	for(;(c=gc())<'0'||c>'9';);
	for(;b[++m].x=c-48,(c=gc())<='9'&&c>='0';);
	fo(i,0,n>>1)swap(a[i],a[n-i]);
	fo(i,0,m>>1)swap(b[i],b[m-i]);
	for(Q=1;Q<=n+m;Q<<=1);ny=1./Q;
	fo(i,1,Q)h[i]=(h[i>>1]>>1)|(i&1?Q>>1:0);
	dft(a);dft(b);
	fo(i,0,Q){
		A.x=a[i].x*b[i].x-a[i].y*b[i].y;
		A.y=a[i].x*b[i].y+a[i].y*b[i].x;
		a[i]=A;
	}
	fo(i,1,Q>>1)swap(a[i],a[Q-i]);
	dft(a);
	int y=0;
	n+=m-2;
	fo(i,0,n){
		aa[i]=(int)(a[i].x*ny+0.5)+y;
		y=aa[i]/10;
		aa[i]=aa[i]%10;
	}
	if(y)aa[++n]=y;
	fd(i,0,n)put(aa[i]+48);
	flush();
}

评测结果