FFT高精度乘法板子

这几天学习了FFT,第一道题就是高精度,存个板子记录一下。

//FFT multy
#include<set>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define N 300000
#define pi acos(-1)
#define ll long long
#define lowbit(x) (x&-x)
#define maxint 2147483647
#define abs(x) (a<0?-a:a)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ckmax(a,b) (a=max(a,b))
#define ckmin(a,b) (a=min(a,b))
#define isd(c) ('0'<=c&&c<='9')
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c='\0'){char ch[(sizeof(T)+1)<<1];if (x<0) putchar('-'),x=-x;
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!='\0') putchar(c);
}
struct cpx {double r,i;cpx(){}
    cpx(double x, double y) {r=x;i=y;}
    inline cpx operator*(const cpx&x)const {return cpx(r*x.r-i*x.i,r*x.i+i*x.r );}
    inline cpx operator*=(const cpx&x) {return*this=*this*x;}
    inline cpx operator+(const cpx&x)const {return cpx(r+x.r,i+x.i);}
    inline cpx operator-(const cpx&x)const {return cpx(r-x.r,i-x.i);}
} a[N],b[N];
int n,L,R[N],c[N];
char ch[N];
inline void fft(cpx*a,int f) {
    for (int i=0;i<n;++i) if(i<R[i]) swap(a[i],a[R[i]]);
    for(register int i=1; i<n; i<<=1) {
        cpx wn(cos(pi/i),f*sin(pi/i));
        for(register int j=0; j<n; j+=(i<<1)) {
            cpx w(1,0);
            for(register int k=0; k<i;++k,w*=wn) {
                cpx x=a[j+k],y=w*a[j+k+i];
                a[j+k]=x+y,a[j+k+i]=x-y;
            }
        }
    }
    if(f==-1) for (int i=0;i<n;++i) a[i].r/=n;
}
int main() {
    read(n);n--;
    scanf("%s",ch);for (int i=0;i<=n;++i) a[i].r=ch[n-i]-'0';
    scanf("%s",ch);for (int i=0;i<=n;++i) b[i].r=ch[n-i]-'0';
    int m=2*n;for(n=1; n<=m ; n<<=1)++L;
    for (int i=0;i<n;++i) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
    fft(a,1);fft(b,1);for (int i=0;i<=n;++i) a[i]*=b[i];fft(a,-1);
    for (int i=0;i<=m;++i) c[i]=(int)(a[i].r+0.1);
    for (int i=0;i<=m;++i) if(c[i]>=10) {
        c[i+1]+=c[i]/10,c[i]%=10;if(i==m) m++;
    }
    while(m) if(c[m]) break;else m--;
    while(~m) wt(c[m--]);putchar('\n');
    return 0;
}

点我回到主页