这几天学习了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; }