【大整数乘法】

article/2025/9/14 5:12:51

问题

2.伪代码

理想情况下，XY位数相同

Mul(long long x,long long y,int num){Fh<--(x*y>0)?1:-1;x<--|x|; y<--|y|;if(num == 0)then return 0;else if(num==1) then return fh*x*y;else{x_high<--x/10^(num/2);x_low<--x mod 10^(num/2);y_high<--y/10^(num/2);y_low<--y_mod 10^(num/2);High<--mul(x_high,y_high, num/2);Low<--mul(x_low,y_low,num/2);Mid<--mul((x_high-x_low),(y_low-y_high),num/2)+High+Low;return fh* High*10^num +Mid*10^(num/2)+Low;}
}
Main(){Input:A,B;Temp<--A;While(temp) do{n++;temp<--temp/10;
}Return mul(a,b,n);
}

非理想情况下，XY位数不同

Mul(long long x, int numx, long long y, int numy){Fh<--(x*y>0)?1:-1;x<--|x|; y<--|y|;if(numx == 0 || numy == 0) then return 0;else if((numx == 1 && numy == 1) || numx == 1 || numy == 1) then return fh*x*y;else{x_low <-- numx / 2;x_high<-- numx - x_low;y_low <-- numy / 2;y_high<-- numy - y_low;//记录XY分的高低位的位数。A <-- x / 10^x_low;B <-- x % 10^x_low;C <-- y / 10^y_low;D <-- y % 10^y_low;//获取XY的高低位的数值。AC<--mul(A, x_high, C, y_high);BD<-- mul(B, x_low, D, y_low);ABCD<--mul(( (A *10^x_low) - B), x_high, (D - (C * 10^y_low)), y_high);return fh * (2 * AC * 10^(x_low+y_low) + ABCD + 2 * BD);}
} 
Main(){Input:A,B;Temp<--A;
While(temp) do{n1++;temp<--temp/10;
}
Temp<--B;
While(temp) do{n2++;temp<--temp/10;
}Return mul(a,n1,b,n2);
}

源代码及结果

理想情况下，XY位数相同

#include<bits/stdc++.h>
using namespace std;
#define sign(x) ((x>0)? 1:-1)long long mul(long long x,long long y,int num){int fh=sign(x)*sign(y);x=x>0?x:-x;y=y>0?y:-y;if(num==0)return 0;else if(num==1)		return fh*x*y;else{long long x_high=x/(int)pow(10,(int)(num/2));long long x_low=x%(int)pow(10,(int)(num/2));long long y_high=y/(int)pow(10,(int)(num/2));long long y_low=y%(int)pow(10,(int)(num/2));long long High=mul(x_high,y_high,(int)(num/2));long long Low=mul(x_low,y_low,(int)(num/2));long long Mid=mul((x_high-x_low),(y_low-y_high),(int)(num/2))+High+Low;return fh*(long long)(High*pow(10,(int)(num/2)+(int)(num/2))+Mid*pow(10,(int)(num/2))+Low);}
}
int main(){long long a,b,c,temp;int n=0;while(cin>>a>>b){temp=a;while(temp){n++;temp=temp/10;}c=mul(a,b,n);cout<<c<<endl;}return 0;
}

运行结果：

非理想情况下，XY位数不同

#include <bits/stdc++.h>
using namespace std;
#define sign(x) ((x>0)? 1:-1)long long  mul(long long x, int numx, long long y, int numy) {int fh = sign(x) * sign(y);x = x > 0 ? x : -x;y = y > 0 ? y : -y;if (numx == 0 || numy == 0)return 0;else if ((numx == 1 && numy == 1) || numx == 1 || numy == 1) {return fh * x * y;} else {int x_low = numx / 2;int x_high = numx - x_low;int y_low = numy / 2;int y_high = numy - y_low;long long A = x / (int)pow(10, x_low);long long B = x % (int)pow(10, x_low);long long C = y / (int)pow(10, y_low);long long D = y % (int)pow(10, y_low);long long AC = mul(A, x_high, C, y_high);long long BD = mul(B, x_low, D, y_low);long long ABCD = mul(((long long)(A * pow(10, x_low)) - B), x_high, (D - (long long)(C * pow(10, y_low))), y_high);return fh * (long long)(2 * AC * pow(10, (x_low + y_low)) + ABCD + 2 * BD);}
}int main() {long long a, b, c, temp;int n1 = 0, n2 = 0;while (cin >> a >> b) {temp = a;while (temp) {n1++;temp = temp / 10;}temp = b;while (temp) {n2++;temp = temp / 10;}c = mul(a, n1, b, n2);cout << c << endl;n1 = 0;n2 = 0;}return 0;
}

运行结果：