http://acm.hdu.edu.cn/showproblem.php?pid=1402
快速傅里叶变换优化的高精度乘法。
https://blog.csdn.net/ggn_2015/article/details/68922404 这个写的很详细了。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<iostream> 6 #include<vector> 7 #include<complex> 8 using namespace std; 9 #define LL long long 10 const int maxn=150010; 11 typedef complex< double >cd; 12 char s1[maxn]={},s2[maxn]={}; 13 int ans[maxn]={}; 14 int rev[maxn]={}; int s,bit; 15 cd a[maxn]={},b[maxn]={}; 16 double Pi; 17 inline void getrev(){ for(int i=0;i<s;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1)); } 18 inline void fft(cd *c,int n,int dft){ 19 for(int i=1;i<=s;i++)if(rev[i]>i)swap(c[i],c[rev[i]]); 20 for(int step=1;step<n;step<<=1){ 21 cd shu=exp(cd(0,dft*Pi/step)); 22 for(int i=0;i<n;i+=step<<1){ 23 cd z=cd(1,0); 24 for(int j=i;j<i+step;j++){ 25 cd x=c[j];cd y=c[j+step]*z; 26 c[j]=x+y; c[j+step]=x-y; 27 z*=shu; 28 } 29 } 30 } 31 if(dft==-1)for(int i=0;i<n;i++)c[i]/=n; 32 } 33 int main(){ 34 cd cle(0,0);Pi=2.0*acos(0.0); 35 while(~scanf("%s%s",s1,s2)){ 36 memset(rev,0,sizeof(rev)); 37 int l1=strlen(s1),l2=strlen(s2),n=l1+l2-1; 38 bit=1;s=2; for(;s<n;++bit)s<<=1; 39 getrev(); 40 for(int i=1;i<=s;i++){a[i]=cle;b[i]=cle;} 41 for(int i=0;i<l1;i++)a[i]=(double)(s1[l1-i-1]-'0'); 42 for(int i=0;i<l2;i++)b[i]=(double)(s2[l2-i-1]-'0'); 43 fft(a,s,1);fft(b,s,1); 44 for(int i=0;i<s;i++)a[i]*=b[i]; 45 fft(a,s,-1); 46 memset(ans,0,sizeof(ans)); 47 for(int i=0;i<s;i++){ 48 ans[i]+=(int)(a[i].real()+0.5); 49 ans[i+1]+=ans[i]/10; 50 ans[i]%=10; 51 } 52 int i; 53 for(i=l1+l2;!ans[i]&&i>0;--i); 54 if(i==0)printf("%d ",ans[0]); 55 else{ 56 for(;i>=0;--i)printf("%d",ans[i]); 57 printf(" "); 58 } 59 } 60 return 0; 61 }