太逊了,只能压两位,大佬们有什么办法压到4位以上吗。
#include <bits/stdc++.h>
#include <iomanip>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const double PI=3.1415926535;
const int N=1<<21;
int ans[N],rev[N];
complex<double> xa[N],xb[N],w_table[N];
void FFT(complex<double> a[],int n,int inv){
rep(i,0,n)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int mid=1;mid<n;mid<<=1){
double ag=PI/mid;complex<double> wn(cos(ag),-inv*sin(ag)),w(1,0);
rep(j,0,mid)w_table[j]=w,w*=wn;
for(int i=0;i<n;i+=mid*2)rep(j,0,mid){
complex<double> x=a[i+j],y=w_table[j]*a[i+j+mid];
a[i+j]=x+y,a[i+j+mid]=x-y;
}
}
if(inv==-1)rep(i,0,n)a[i]/=n;
}
void hpm(string a,string b){
if(a=="0"||b=="0"){cout<<'0';return;}
reverse(a.begin(),a.end()),reverse(b.begin(),b.end());
int la=0,lb=0;
rep(i,0,a.size()){
int pos=i/2,num=a[i]-'0';
if(i%2==0)xa[pos]=num;
else xa[pos]+=pow(10,i%2)*num;
la=pos+1;
}
rep(i,0,b.size()){
int pos=i/2,num=b[i]-'0';
if(i%2==0)xb[pos]=num;
else xb[pos]+=pow(10,i%2)*num;
lb=pos+1;
}
int len=1,bit=0;
while(len<la+lb)len<<=1,bit++;
rep(i,0,len)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
FFT(xa,len,1),FFT(xb,len,1);
rep(i,0,len)xa[i]*=xb[i];
FFT(xa,len,-1);
rep(i,0,len)ans[i]=int(xa[i].real()+0.5);
rep(i,0,len-1)ans[i+1]+=ans[i]/100,ans[i]%=100;
int pos=len-1;
while(pos>0&&ans[pos]==0)pos--;
cout<<ans[pos];
for(int i=pos-1;i>=0;i--)cout<<setfill('0')<<setw(2)<<ans[i];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
string a,b;
cin>>a>>b;
hpm(a,b);
return 0;
}