代码

#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
namespace bigint
{
	int n,m,i,j,rev[4000005],len,ans[4000005];
	struct fushu
	{
		double x,y;
		fushu operator +(fushu z)
		{
			return (fushu){x+z.x,y+z.y};
		}
		fushu operator -(fushu z)
		{
			return (fushu){x-z.x,y-z.y};
		}
		fushu operator *(fushu z)
		{
			return (fushu){x*z.x-y*z.y,x*z.y+y*z.x};
		}
		fushu operator *(double z)
		{
			return (fushu){x*z,y*z};
		}
		fushu operator /(double z)
		{
			return (fushu){x/z,y/z};
		}
	};
	fushu a[4000005],b[4000005];
	int getrev(int l2)
	{
		memset(rev,0,sizeof(rev));
		int len=1,cnt=0;
		while (len<=l2)
		{
			len*=2;
			cnt++;
		}
		for (i=1;i<len;i++) rev[i]=(rev[i/2]/2)|((i&1)<<(cnt-1));
		return len;
	}
	void fft(fushu num[],int len,int op)
	{
		int i,j,k;
		for (i=0;i<len;i++)
		{
			if (rev[i]>i) swap(num[i],num[rev[i]]);
		}
		for (i=2;i<=len;i*=2)
		{
			fushu y=(fushu){cos(3.141592653589793*2.0/((double)i)),sin(-op*3.141592653589793*2.0/((double)i))};
			for (j=0;j<len;j+=i)
			{
				fushu x=(fushu){1,0};
				for (k=j;k<j+i/2;k++)
				{
					fushu z=num[k],w=num[k+i/2]*x;
					fushu sum=z+w,sub=z-w;
					num[k]=sum;
					num[k+i/2]=sub;
					x=x*y;
				}
			}
		}
		if (op==-1)
		{
			for (i=0;i<len;i++) num[i]=num[i]/len;
		}
	}
	string mul(string sa,string sb)
	{
		len=getrev(sa.size()+sb.size());
		//cerr<<len<<endl;
		reverse(sa.begin(),sa.end());
		reverse(sb.begin(),sb.end());
		for (i=0;i<sa.size();i++) a[i]=(fushu){sa[i]-'0',0};
		for (;i<=len;i++) a[i]=(fushu){0,0};
		for (i=0;i<sb.size();i++) b[i]=(fushu){sb[i]-'0',0};
		for (;i<=len;i++) b[i]=(fushu){0,0};
		fft(a,len,1);
		fft(b,len,1);
		for (i=0;i<len;i++) a[i]=a[i]*b[i];
		fft(a,len,-1);
		for (i=0;i<len;i++) ans[i]=(int)(a[i].x+0.5);
		for (i=0;i<len;i++)
		{
			ans[i+1]+=ans[i]/10;
			ans[i]%=10;
		}
		for (i=len-1;i&&(!ans[i]);i--);
		string res;
		for (;~i;i--) res.push_back(ans[i]+'0');
		return res;
	}
	string add(string sa,string sb)
	{
		len=max(sa.size(),sb.size());
		//cerr<<len<<endl;
		reverse(sa.begin(),sa.end());
		reverse(sb.begin(),sb.end());
		int s=0;
		string res="";
		for (i=0;i<sa.size()||i<sb.size()||s;i++)
		{
			if (i<sa.size()) s+=sa[i]-'0';
			if (i<sb.size()) s+=sb[i]-'0';
			res.push_back(s%10+'0');
			s/=10;
		}
		reverse(res.begin(),res.end());
		return res;
	}
	string sub(string sa,string sb)
	{
		int la=sa.length(),lb=sb.length(),i,g=0,s=0;
		if (la<lb) return "-1";
		if (la==lb&&sa<sb) return "-1";
		reverse(sa.begin(),sa.end());
		reverse(sb.begin(),sb.end());
		vector<int> num;
		for (i=0;i<la;i++)
		{
			if (i<lb) num.push_back(sa[i]-sb[i]); else num.push_back(sa[i]-'0');
		}
		string ans;
		for (i=0;i<num.size();i++)
		{
			while (num[i]<0)
			{
				num[i]+=10;
				num[i+1]--;
			}
		}
		reverse(num.begin(),num.end());
		for (i=0;i<num.size()-1;i++) if (num[i]!=0) break;
		for (;i<num.size();i++) ans.push_back(num[i]+'0');
		return ans;
	}
	string div(string sa,string sb)
	{
		string ans,tmp;
		int la=sa.length(),lb=sb.length(),i,j=0,g=0,s=0;
		tmp=sb;
		if (sub(sa,sb)=="-1") return "0";
		while (sub(sa,tmp)!="-1")
		{
			tmp.push_back('0');
			j++;
		}
		tmp.erase(tmp.length()-1);
		j--;
		ans.resize(j+1,'0');
		while (j>=0)
		{
			for(;;)
			{
				string nw=sub(sa,tmp);
				if (nw!="-1")
				{
					sa=nw;
					ans[j]++;
				}
				else break;
				//cerr<<sa<<' '<<ans<<endl;
			}
			j--;
			tmp.erase(tmp.length()-1,1);
		}
		reverse(ans.begin(),ans.end());
		return ans;
	}
};
string s,t;
char ss[1000005];
int main() {
scanf("%s\n",ss);s=ss;
scanf("%s\n",ss);t=ss;
puts(bigint::mul(s,t).c_str());
	return 0;
}

评测结果