大整数乘法 给定X和Y都是n位整数，计算乘积XY。分治算法思想，将n位X和Y分成2段，每段n/2位。则X分为AB两段，Y分为CD...

（一）实验项目名称：大整数乘法 实验描述：给定X和Y都是n位整数，计算乘积XY。分治算法思想，将n位X和Y分成2段，每段n/2位。则X分为AB两段，Y分为CD两段。 有X=A*(10)^(n/2)+B，Y=C*(10)^(n/2)+D；XY=(A*(10)^(n/2)+B)(C*(10)^(n/2)+D)=AC*(10)^n+(AD+BC)*(10)^(n/2)+BD。 证明及详细分析参见教材16页。 编程任务： 给定两个数X和Y，打印出X和Y采用分治法计算X*Y过程中，拆分的ABCD四个部分的值，和最终的计算结果。 Input 输入为两个整数X，Y Output 采用分治法求解过程中计算的ABCD的值，和最终X*Y的结果 输出结果中间有空格 Sample Input 12 12 Sample Output 1 2 1 2 12 * 12 = 144 #include <iostream.h> #include <math.h> long pow(int n) { int s=10; for(int i=1;i<n;i++) { s=s*10; } return s; } int num(long x) { int s=0; while(x) { x=x/10; s++; } return s; } long mult(long a,long b) { int n=num(a); long m; long s; long A,B,C,D; if(n>1) { m=(long)pow(n/2); A=a/m; B=a%m; C=b/m; D=b%m; s=mult(A,C)*m*m+(mult(A,D)+mult(B,C))*m+mult(B,D); } else return a*b; return s; } int main() { long x,y; cin>>x>>y; if(num(x) == 1) cout<<"0"<<" "<<x<<" "<<"0"<<" "<<y<<endl; else{ cout<<(x/(long)pow( num(x)/2))<<" "<<x%(long)pow(num(x)/2)<<" "<<y/(long)pow(num(x)/2)<<" "<<y%(long)pow(num(x)/2)<<endl; } cout<<x<<" "<<"*"<<" "<<y<<" "<<"="<<" "; cout<<mult(x,y)<<endl; return 0; }