題目:輸入兩個大整數,用數組保存每一位數,然後用分治法計算;
思路:輸入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; }