FFT求调
查看原帖
FFT求调
456675
a_sad_soul楼主2024/3/17 14:19
#include<bits/stdc++.h>
#define MAXN 4000050
using namespace std;
struct Complex{
    double Re=0.0,Im=0.0;
    Complex operator*(Complex x)
    {
        Complex re;
        re.Re=x.Re*Re-x.Im*Im;
        re.Im=x.Re*Im+x.Im*Re;
        return re;
    }
    Complex operator+(Complex x)
    {
        Complex re;
        re.Re=x.Re+Re;
        re.Im=x.Im+Im;
        return re;
    }
    Complex operator-(Complex x)
    {
        Complex re;
        re.Re=Re-x.Re;
        re.Im=Im-x.Im;
        return re;
    }
    Complex(double a,double b ){Re=a,Im=b;}
    Complex(){Re=0,Im=0;}
    Complex operator/(double x){Complex Re=*this;Re.Re/=x,Re.Im/=x;return Re;}
};
Complex tmp[MAXN];
double Pi=3.1415926;

void FFT(Complex *x,int n,int rev)
{
    if(n==1)return ;
    for(int i=0;i<n;++i)tmp[i]=x[i];//2k put on left,2k+1 put on right
    for(int i=0;i<n;++i)
        if(i&1)x[n/2+i/2]=tmp[i];
        else x[i/2]=tmp[i];
    Complex *g=x,*h=x+n/2;
    FFT(g,n/2,rev),FFT(h,n/2,rev);
    Complex cur=Complex(1,0),next=Complex(cos(2*Pi/n),sin(2*Pi*rev/n));
    for(int k=0;k<n/2;++k)
    {
        tmp[k]=g[k]+cur*h[k];
        tmp[k+n/2]=g[k]-(cur*h[k]);
        cur=cur*next;
    }
    for(int i=0;i<n;++i)x[i]=tmp[i];
    return ;
}
string a,b;
Complex x1[MAXN],x2[MAXN];
int ans[MAXN];
int main()
{
    cin>>a>>b;
    int lena=a.size(),lenb=b.size(),len=1;    
    while(len<lena*2||len<lenb*2)len<<=1;
    for(int i=0;i<lena;++i)x1[i]=Complex(a[lena-1-i]-'0',0);
    for(int i=lena;i<len;++i)x1[i]=Complex(0,0);
    for(int i=0;i<lenb;++i)x2[i]=Complex(b[lenb-1-i]-'0',0);
    for(int i=lenb;i<len;++i)x2[i]=Complex(0,0);
    FFT(x1,len,1),FFT(x2,len,1);
    for(int i=0;i<len;++i)x1[i]=x1[i]*x2[i];
    FFT(x1,len,-1);
    for(int i=0;i<len;++i)ans[i]=int(x1[i].Re/(double)len);
    for(int i=0;i<len;++i)ans[i+1]+=ans[i]/10,ans[i]%=10;
    len =lena+lenb-1;
    while(ans[len]==0&&len)--len;
    for(int i=len;i>=0;--i)putchar(ans[i]%10+'0');
    return 0;
}
2024/3/17 14:19
加载中...