这就是FFT压位的极限吗
查看原帖
这就是FFT压位的极限吗
1288642
lmn985楼主2025/6/27 12:04

太逊了,只能压两位,大佬们有什么办法压到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;
}
2025/6/27 12:04
加载中...