RE求助,我在本地没问题
查看原帖
RE求助,我在本地没问题
553501
可爱的小棉羊楼主2023/9/14 15:24
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> cp;
const double pi=acos(-1);
cp a[2000006],b[2000006];
int ans[2000006];
int pos[2000006];
string s1,s2;
void fft(cp *a,int n,int f){
	for(int i=0;i<n;i++)if(i<pos[i])swap(a[i],a[pos[i]]);
	for(int h=1;h<n;h*=2){
		cp wn1=exp(cp(0,pi*f/h));
		for(int i=0;i<n;i+=h*2){
			cp w(1,0);
			for(int j=i;j<i+h;j++){
				cp x=a[j];
				cp y=a[j+h]*w;
				a[j]=x+y;
				a[j+h]=x-y;
				w*=wn1;
			}
		}
	}
	if(f==-1){
		for(int i=0;i<n;i++)a[i]/=n;
	}
}
int main(){
	cin<<s1<<s2;
	for(int i=0;i<s1.size();i++)a[i]=(double)(s1[s1.size()-i-1]-'0');
	for(int i=0;i<s2.size();i++)b[i]=(double)(s2[s2.size()-i-1]-'0');
	int k=1;
	int s=2;
	while((1<<k)<s1.size()+s2.size()-1)k++,s<<=1;
	
	for(int i=0;i<s;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(k-1));
	fft(a,s,1);
	fft(b,s,1);
	for(int i=0;i<s;i++)a[i]*=b[i];
	fft(a,s,-1);
	for(int i=0;i<s;i++){
		ans[i]+=(int)(a[i].real()+0.5);
		ans[i+1]+=ans[i]/10;
		ans[i]%=10;
	}
	while(!ans[s]&&s>-1)s--;
	if(s==-1)cout<<0<<endl;
	else{
		for(int i=s;i>=0;i--)printf("%d",ans[i]);
	}
	return 0;
} 
2023/9/14 15:24
加载中...