首页 > 代码库 > 大整数乘法（分治法）
大整数乘法（分治法）
题目：输入两个大整数，用数组保存每一位数，然后用分治法计算；
思路：输入X Y，X高位用A数组保存，低位用B数组保存，Y高位用C数组保存，低位用D数组保存，则：X=A*10^(n/2)+B Y=C*10^(n/2)+D
分治方法：X*Y=A*C*10^n+((A-B)*(D-C)+A*C+B*D)*10^(n/2)+B*D;
代码如下：
#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>#include <cmath>#include <map>#include <vector>using namespace std;void add(int a[],int b[],int c[]){ int tot=0; int maxn=max(a[0],b[0]); for(int i=2; i<=maxn+2; i++) { c[i]=(a[i]+b[i]+tot)%10; tot=(a[i]+b[i]+tot)/10; } c[0]=maxn+(c[maxn+2]>0); c[1]=a[1];}void sub(int a[],int b[],int c[]){ int tot=0; int maxn=max(a[0],b[0]); c[1]=1; for(int i=maxn+1; i>=2; i--) { if(a[i]>b[i]) break; if(a[i]<b[i]) { swap(a,b); c[1]=-1; break; } } for(int i=2; i<=maxn+1; i++) { c[i]=a[i]+tot-b[i]; if(c[i]<0) { c[i]=c[i]+10; tot=-1; } else tot=0; } c[0]=a[0];}void process(int a[],int b[],int c[],int g){ if(a[1]>0) { if(b[1]*g>0) add(a,b,c); else sub(a,b,c); } else { if(b[1]*g>0) sub(b,a,c); else add(a,b,c); }}void Move(int a[],int n){ for(int i=a[0]+1; i>=2; i--) a[i+n]=a[i]; for(int i=2; i<=n+1; i++) a[i]=0; a[0]+=n;}void print(int c[]){ int i; if(c[1]<0) cout<<"-"; for(i=c[0]+1; i>=2; i--) if(c[i]) break; for(; i>=2; i--) cout<<c[i]; cout<<endl;}void duiqi(int a[],int b[]){ int maxn=max(a[0],b[0]); int tmp=1; for(int i=0;i<=10;i++) { if(tmp>=maxn) break; tmp<<=1; } a[0]=tmp; b[0]=tmp;}void calc(int a[],int b[],int c[]){ if(a[0]==1) { int tmp=a[2]*b[2]; c[0]=1; c[2]=tmp%10; if(tmp>=10) { c[3]=tmp/10; c[0]++; } c[1]=a[1]*b[1]; return; } int A[1000],B[1000],C[1000],D[1000],E[1000],F[1000]; int m1[1000],m2[1000],m3[1000]; memset(A,0,sizeof(A)); memset(B,0,sizeof(B)); memset(C,0,sizeof(C)); memset(D,0,sizeof(D)); memset(E,0,sizeof(E)); memset(F,0,sizeof(F)); memset(m1,0,sizeof(m1)); memset(m2,0,sizeof(m2)); memset(m3,0,sizeof(m3)); for(int i=1; i<=a[0]/2+1; i++) B[i]=a[i]; B[0]=a[0]/2; for(int i=a[0]/2+2; i<=a[0]+1; i++) A[i-a[0]/2]=a[i]; A[0]=a[0]/2; A[1]=a[1]; for(int i=1; i<=b[0]/2+1; i++) D[i]=b[i]; D[0]=b[0]/2; for(int i=b[0]/2+2; i<=b[0]+1; i++) C[i-b[0]/2]=b[i]; C[0]=b[0]/2; C[1]=b[1]; process(A,B,E,-1); process(D,C,F,-1); calc(A,C,m1); calc(E,F,m2); calc(B,D,m3); process(m2,m1,E,1); process(E,m3,F,1); Move(m1,a[0]); Move(F,a[0]/2); process(m1,F,E,1); process(E,m3,c,1);}int main(){ int a[1000],b[1000],c[2000]; char s1[1000],s2[1000]; cin>>s1>>s2; a[0]=strlen(s1)-1; if(s1[0]==‘-‘) a[1]=0; else a[1]=1; a[0]+=a[1]; for(int i=2; i<=a[0]+1; i++) a[i]=s1[a[0]-a[1]-i+2]-‘0‘; b[0]=strlen(s2)-1; if(s2[0]==‘-‘) b[1]=0; else b[1]=1; b[0]+=b[1]; for(int i=2; i<=b[0]+1; i++) b[i]=s2[b[0]-b[1]-i+2]-‘0‘; a[1]+=a[1]-1; b[1]+=b[1]-1; duiqi(a,b); calc(a,b,c); print(c); return 0;}
大整数乘法（分治法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。