【51NOD1028】大数乘法 V2

2019-11-08 18:39:30

字体：大中小

来源：转载

供稿：网友

╰(￣▽￣)╭

给出2个大整数A,B，计算A*B的结果。 (A,B的长度 <= 100000，A,B >= 0）

(⊙ ▽ ⊙)

把大整数A $A$ 看做一个次数界为lenA $len_A$ 的多项式A(x) $A(x)$ ，其中x=10 $x=10$ ，同样，把B $B$ 看做一个次数界为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--) PRintf("%d",ans[n]); return 0;}

(⊙v⊙)

Pay Attention

1.read()中，不要把len打成lena；翻转大整数时，是从0枚举到(len+1)/2；2.getn()中，n最后要再乘一次2，因为：A*B的次数界是lena*lenb。3.maxn要开到4倍；4.pi=acos(-1)；5.当对一个小数x用int()取整时，需要打成int(x+eps)，其中，eps=10e-6。

上一篇：SDUT 2143 - 图结构练习——最短路径（dijkstra+模板）

下一篇：【第四章】资源之 4.2 内置Resource实现 ——跟我学spring3

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注