大整数的乘法 cpp

大整数的乘法可以使用分治算法来实现。首先，将两个大整数分别拆分成两部分，然后对每一部分进行乘法运算。最后将结果相加。这种方法的时间复杂度为O(n^log2(3))。
下面是一个C++的示例代码，演示了如何使用分治算法实现大整数的乘法：
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

const int maxn = 205;

// 大整数相加
string add(string num1, string num2) {
string result = "";
int carry = 0;
int len1 = num1.length();
int len2 = num2.length();

while(len1 > 0 || len2 > 0 || carry > 0) {
int digit1 = (len1 > 0) ? num1[--len1] - '0' : 0;
int digit2 = (len2 > 0) ? num2[--len2] - '0' : 0;
int sum = digit1 + digit2 + carry;
result = to_string(sum % 10) + result;
carry = sum / 10;
}

return result;
}

// 大整数相减
string subtract(string num1, string num2) {
string result = "";
int borrow = 0;
int len1 = num1.length();
int len2 = num2.length();

while(len1 > 0 || len2 > 0) {
int digit1 = (len1 > 0) ? num1[--len1] - '0' : 0;
int digit2 = (len2 > 0) ? num2[--len2] - '0' : 0;
int diff = digit1 - digit2 - borrow;

if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}

result = to_string(diff) + result;
}

return result;
}

// 大整数乘法
string multiply(string num1, string num2) {
int len1 = num1.length();
int len2 = num2.length();

if (len1 == 0 || len2 == 0) {
return "0";
}

if (len1 == 1 &amp;&amp; len2 == 1) {
return to_string((num1[0] - '0') * (num2[0] - '0'));
}

// 将两个大整数分成两部分
int mid = min(len1, len2) / 2;
string num1_high = num1.substr(0, len1 - mid);
string num1_low = num1.substr(len1 - mid);
string num2_high = num2.substr(0, len2 - mid);
string num2_low = num2.substr(len2 - mid);

// 分别计算四个乘积
string ac = multiply(num1_high, num2_high);
string bd = multiply(num1_low, num2_low);
string ad = multiply(num1_high, num2_low);
string cb = multiply(num1_low, num2_high);

// 结果相加
string result = add(add(ac + string(mid * 2, '0'), bd), add(ad, cb));

return result;
}

int main() {
string num1, num2;
cin >> num1 >> num2;

string result = multiply(num1, num2);
cout << result << endl;

return 0;
}
登录后复制