大整数的乘法
std::vector<int> solve(std::string X, std::string Y) {
std::vector<int> result(255, 0);
std::function<void(std::string, std::string, int)> multiply = [&](std::string s, std::string t, int pos) {
int n = (int) s.size(), m = (int) t.size();
if (n == 0 m == 0) { // 位数为0时
return ;
} else if (n == 1 && m == 1) { // 递归到当前数组s和t的位数全为1时
result[pos] += (s[0] - '0') * (t[0] - '0');
return ;
} else { // 当数组s和t的位数至少有一个不为1时
int n1 = n / 2; // n1为B的位数,B属于低位的那一部分
int n2 = n - n1; // n2为A的位数,A属于高位的那一部分
int m1 = m / 2; // m1为D的位数,D属于低位的那一部分
int m2 = m - m1; // m2为D的位数,C属于高位的那一部分
std::string A = s.substr(0, n2); // 获取s的高位部分A
std::string B = s.substr(n2); // 获取s的低位部分B
std::string C = t.substr(0, m2); // 获取t的高位部分C
std::string D = t.substr(m2); // 获取t的低位部分D
multiply(A, C, pos + n1 + m1); // AC,在result[pos+n1+m1]的位置存储AC,也是说偏移pos+n1+m1位,pos初始化为0
multiply(B, C, pos + m1); // BC,偏移pos+m1位
multiply(A, D, pos + n1); // AD,偏移pos+1位
multiply(B, D, pos); // BD,偏移pos位
}
};
multiply(X, Y, 0);
int len = (int) X.size() + (int) Y.size();
for (int i = 0; i <= len; i++) {
int now = result[i] % 10;
int bit1 = result[i] / 10 % 10;
int bit2 = result[i] / 100;
result[i] = now;
result[i + 1] += bit1;
result[i + 2] += bit2;
}
while (result.back() == 0) {
result.pop_back();
}
return result;
}
最后更新:
2024年1月2日 21:37:12
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42