【51NOD1028】大數(shù)乘法 V2

2019-11-08 18:39:30

字體：大中小

來源：轉載

供稿：網(wǎng)友

╰(￣▽￣)╭

給出2個大整數(shù)A,B，計算A*B的結果。 (A,B的長度 <= 100000，A,B >= 0）

(⊙ ▽ ⊙)

把大整數(shù)A $A$ 看做一個次數(shù)界為lenA $len_A$ 的多項式A(x) $A(x)$ ，其中x=10 $x=10$ ，同樣，把B $B$ 看做一個次數(shù)界為lenB $len_B$ 的多項式B(x) $B(x)$ ，其中x=10 $x=10$ 。

然后套上快速傅里葉變換。

(￣～￣)

#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>#include<math.h>using namespace std;const char* fin="ftt.in";const char* fout="fttx.out";const int inf=0x7fffffff;const double pi=acos(-1),eps=10e-6;const int maxn=400007;struct Z{ double x,y; Z(double _x=0,double _y=0){x=_x;y=_y;} Z Operator +(const Z &b){return Z(x+b.x,y+b.y);} Z operator -(const Z &b){return Z(x-b.x,y-b.y);} Z operator *(const Z &b){return Z(x*b.x-y*b.y,x*b.y+y*b.x);}}a[maxn],b[maxn],t[maxn];int ans[maxn],lena,lenb,n,N,i,j,k;void read(Z *a,int &len){ int i,j,k; char ch=getchar(); while (ch<'0' || ch>'9') ch=getchar(); while (ch>='0' && ch<='9') a[len++]=ch-'0',ch=getchar(); for (i=0;i<(len+1)/2;i++) swap(a[i],a[len-i-1]);}void getn(){ int i,j,k=max(lena,lenb); for (n=1;n<k;n<<=1) N++; n<<=1;N++;}int fan(int v){ int i=N,k=0; while (i--){ k=(k<<1)+(v&1); v>>=1; } return k;}void fft(Z *a,int sig){ int i,j,k,m; for (i=0;i<n;i++) t[fan(i)]=a[i]; for (m=2;m<=n;m<<=1){ int ha=m/2; for (i=0;i<ha;i++){ Z w(cos(i*sig*pi/ha),sin(i*sig*pi/ha)); for (j=i;j<n;j+=m){ Z u=t[j],v=w*t[j+ha]; t[j]=u+v; t[j+ha]=u-v; } } } for (i=0;i<n;i++) a[i]=t[i];}int main(){ freopen(fin,"r",stdin); freopen(fout,"w",stdout); read(a,lena);read(b,lenb); getn(); fft(a,1); fft(b,1); for (i=0;i<n;i++) a[i]=a[i]*b[i]; fft(a,-1); for (i=0;i<=n;i++){ ans[i]+=int(a[i].x/n+eps); ans[i+1]+=ans[i]/10; ans[i]%=10; } while (!ans[n]) n--; for (;n>=0;n--) (⊙v⊙)

Pay Attention

1.read()中，不要把len打成lena；翻轉大整數(shù)時，是從0枚舉到(len+1)/2；2.getn()中，n最后要再乘一次2，因為：A*B的次數(shù)界是lena*lenb。3.maxn要開到4倍；4.pi=acos(-1)；5.當對一個小數(shù)x用int()取整時，需要打成int(x+eps)，其中，eps=10e-6。