【51nod1028】【大数乘法 V2】【fft】

题目大意

给出2个大整数A,B，计算A*B的结果。

解题思路

fft，然而会卡精度，使用模运算的fft即可解决问题。

code

#include<cmath> #include<cstdio> #include<algorithm> #define LD double #define LL long long #define min(a,b) ((a<b)?a:b) #define max(a,b) ((a>b)?a:b) #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) using namespace std; int const maxn=1e5,g=3,mo=1004535809; int n,m,A,B,w[maxn*4+10],a[maxn*4+10],b[maxn*4+10],t[maxn*4+10]; void read(int &num,int *a){ num=0;int v=0;char ch=getchar(); for(;(ch<'0')||(ch>'9');ch=getchar()); for(;(ch>='0')&&(ch<='9');a[num++]=ch-'0',ch=getchar()); int mx=num/2-1;fo(i,0,mx)swap(a[i],a[num-i-1]); } int up(LD x){return int(x)+((int(x)==x)?0:1);} void DFT(int *a,int tag){ fo(i,0,n-1){ int pos=0; for(int j=0,ii=i;j<m;pos=(pos<<1)+(ii&1),ii=ii>>1,j++); t[pos]=a[i]; } for(int i=2;i<=n;i=i<<1){ int half=i>>1; fo(j,0,half-1){ int wi=(tag>0)?w[n/i*j]:w[n-n/i*j]; for(int k=j;k<n;k+=i){ int x=t[k],y=1ll*wi*t[k+half]%mo; t[k]=(x+y)%mo; t[k+half]=(x-y+mo)%mo; } } } fo(i,0,n-1)a[i]=t[i]; } int Pow(int x,int y){ int z=1; while(y){ if(y&1)z=1ll*z*x%mo; x=1ll*x*x%mo; y=y>>1; } return z; } int main(){ freopen("d.in","r",stdin); freopen("d.out","w",stdout); read(A,a);read(B,b); m=up(log(max(A,B)<<1)/log(2));n=1<<m; w[0]=1;w[1]=Pow(g,(mo-1)/n); fo(i,2,n)w[i]=1ll*w[i-1]*w[1]%mo; DFT(a,1);DFT(b,1); fo(i,0,n-1)a[i]=1ll*a[i]*b[i]%mo; DFT(a,-1); int ni=Pow(n,mo-2); fo(i,0,n-1)a[i]=1ll*a[i]*ni%mo; fo(i,0,n-1){ a[i+1]+=a[i]/10; a[i]%=10; } for(;a[n]==0;n--); fd(i,n,0)putchar(a[i]+'0'); return 0; }