可爱小萌新不会乘法求助,全部tle惹
查看原帖
可爱小萌新不会乘法求助,全部tle惹
774854
qzmoot楼主2024/10/16 19:39
#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5;
int n,m,ans[N],len;
const double Pi=acos(-1.0);
struct clx
{
	double x,y;
	clx (double xx=0,double yy=0){x=xx,y=yy;}
}a[N],b[N];
clx operator + (clx a,clx b)
{
	return clx(a.x+b.x , a.y+b.y);
}
clx operator - (clx a,clx b)
{
	return clx(a.x-b.x , a.y-b.y);
}
clx operator * (clx a,clx b)
{
	return clx(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);
}
void fft(int limit,clx *a,int type)
{
	if(limit==1)
		return ;
	clx a1[limit>>1],a2[limit>>1];
	for(int i=0; i<limit; i+=2)
		a1[i>>1]=a[i],a2[i>>1]=a[i+1];
	fft(limit>>1,a1,type);
	fft(limit>>1,a2,type);
	clx Wn=clx(cos(2.0*Pi/limit) , type*sin(2.0*Pi/limit)),w=clx(1,0);
	for(int i=0;i<(limit>>1);i++,w=w*Wn)
		a[i]=a1[i]+w*a2[i],
		     a[i+(limit>>1)]=a1[i]-w*a2[i];
}
string a1,a2;
int main()
{
	cin>>a1>>a2;
	n=a1.size();
	m=a2.size();
	for(int i=n-1;i>=0; i--)
		a[n-1-i].x=a1[i]-48;
	n--;
	for(int i=m-1;i>=0;i--)
		b[m-1-i].x=a2[i]-48;
	m--;
	int limit=1;
	while(limit<=n+m)
		limit<<=1;
	fft(limit,a,1);
	fft(limit,b,1);
	for(int i=0; i<=limit; i++)
		a[i]=a[i]*b[i];
	fft(limit,a,-1);
	for(int i=0; i<=n+m; i++)
	{
		ans[i]+=(int)(a[i].x/limit+0.5);
		ans[i+1]+=ans[i]/10,ans[i]%=10;
	}
	len=n+m+1;
	while(ans[len])
	{
		ans[len+1]+=ans[len]/10;
		ans[len]%=10;
		len++;
	}
	for(int i=len-1;i>=0;i--)
		printf("%d",ans[i]);
	return 0;
}
2024/10/16 19:39
加载中...