我的karatsuba方法：
// karatsuba multiplication
long long karastuba(long long x, long long y, long long B) {
// 如果x,y是个位数
if (x < B || y < B) {
return x * y;
}
// 计算x和y的位数
long long n = max(to_string(x).size(), to_string(y).size());
long long mid = n / 2;
// 分开为两部分
long long a = x / pow(B, mid);
long long b = x % (long long)pow(B, mid);
long long c = y / pow(B, mid);
long long d = y % (long long)pow(B, mid);
// 卡拉楚巴方法计算
long long ac = karastuba(a, c, B);
long long bd = karastuba(b, d, B);
long long ad_bc = karastuba(a + b, c + d, B) - ac - bd;
long long res = 0;
for (int i = 0; i < 2 * mid; i++) {
res += ac * pow(B, 2 * mid + i);
}
for (int i = 0; i < mid; i++) {
res += ad_bc * pow(B, mid + i);
}
res += bd;
return res;
}
我的main function：
int main() {
long long I1, I2, B;
cin >> I1 >> I2 >> B;
// karatsuba function
long long product = karastuba(I1, I2, B);
cout << product << endl;
return 0;
}
10211001033220013020313211003303321300100220101132012012132211000303113013132010113123003302 311011200232012231 4
我希望的输出：
3303003100312021130111131112011212313232020311201200210322131301032332211032003230122333022213200232110112022
我得到的输出：
-9223018708791985204
我没有懂我哪一部分有错，在这个问题上已经试了一下午了还是没有找到问题出在哪。
参考GPT和自己的思路：
你的代码存在一些问题。首先，在第9行，你使用了 to_string() 函数来计算两个数字的位数，但该函数的时间复杂度是 O(n)，会使你的程序变得非常缓慢。更好的方法是通过循环除以基数 B，直到商为 0，计算数字的位数。
其次，在第12行和第13行，你错误地把第一个数字拆分成了两部分，而其中一部分应该是第二个数字。具体地说，你应该把 x 拆分成 ab^mid + c 和 y 拆分成 db^mid + e，然后对乘积进行以下操作：
ac * B^(2*mid) + ((a+b)(c+d)-ac-bd)*B^mid + bd
因此，第19行到21行的计算结果不正确。你需要改写这三行代码，仔细检查一下。
最后，在第25行和第28行，你使用了 pow() 函数来求幂次方，但该函数的时间复杂度也非常高，会使你的程序变得很慢。更好的方法是通过预处理一个数组，存储不同幂次方的值，然后通过索引来访问该数组。这样可以将时间复杂度降低到 O(1)。
下面是修正后的代码：
#include <iostream>
#include <cstring>
using namespace std;
long long pow(long long x, long long y, long long B) {
long long res = 1;
for (int i = 0; i < y; i++) {
res *= B;
}
return res * x;
}
long long karatsuba(long long x, long long y, long long B, int n) {
if (n == 1) {
return x * y;
}
int mid = n / 2;
long long a = x / pow(B, mid);
long long b = x % pow(B, mid);
long long c = y / pow(B, mid);
long long d = y % pow(B, mid);
long long ac = karatsuba(a, c, B, mid);
long long bd = karatsuba(b, d, B, mid);
long long ad_bc = karatsuba(a - b, c - d, B, mid);
return ac * pow(B, 2 * mid) + (ad_bc + ac + bd) * pow(B, mid) + bd;
}
int main() {
string s1, s2;
long long B;
cin >> s1 >> s2 >> B;
int n = max(s1.size(), s2.size());
if (n > 100) {
cout << "Error: the input numbers are too large." << endl;
return 0;
}
long long x = 0, y = 0;
for (int i = 0; i < s1.size(); i++) {
x += (s1[i] - '0') * pow(B, s1.size() - i - 1);
}
for (int i = 0; i < s2.size(); i++) {
y += (s2[i] - '0') * pow(B, s2.size() - i - 1);
}
long long product = karatsuba(x, y, B, n);
string res = "";
while (product > 0) {
res.push_back('0' + product % B);
product /= B;
}
if (res == "") {
res = "0";
}
reverse(res.begin(), res.end());
cout << res << endl;
return 0;
}
注意，这里的乘法和求幂次方都是手动实现的，因此可能比使用内置函数慢。如果需要更高效的实现，在处理大整数时应该使用更高效的算法，例如 FFT。