Karatsuba 算法：高效解决大数相乘问题

#include #include #include using namespace std;

string add(string a, string b) {//高精度加法 string res; int carry = 0;//进位 for(int i = a.size() - 1, j = b.size() - 1; i >= 0 || j >= 0 || carry; i--, j--) { int x = i >= 0 ? a[i] - '0' : 0; int y = j >= 0 ? b[j] - '0' : 0; int sum = x + y + carry; res += to_string(sum % 10); carry = sum / 10; } reverse(res.begin(), res.end()); return res; }

string sub(string a, string b) {//高精度减法 string res; int borrow = 0;//借位 for(int i = a.size() - 1, j = b.size() - 1; i >= 0 || j >= 0; i--, j--) { int x = i >= 0 ? a[i] - '0' : 0; int y = j >= 0 ? b[j] - '0' : 0; int diff = x - y - borrow; if(diff < 0) { diff += 10; borrow = 1; } else { borrow = 0; } res += to_string(diff); } reverse(res.begin(), res.end()); while(res.size() > 1 && res[0] == '0') res.erase(res.begin());//去掉前导0 return res; }

string multiply(string a, string b) {//高精度乘法 int n = a.size(), m = b.size(); if(n == 0 || m == 0) return "0"; if(a == "0" || b == "0") return "0"; if(n < m) {//保证a的长度不小于b swap(a, b); swap(n, m); } string res = "0"; for(int i = m - 1; i >= 0; i--) { string cur; int carry = 0; for(int j = n - 1; j >= 0; j--) { int x = a[j] - '0'; int y = b[i] - '0'; int product = x * y + carry; cur += to_string(product % 10); carry = product / 10; } if(carry > 0) cur += to_string(carry); reverse(cur.begin(), cur.end()); for(int k = 0; k < m - 1 - i; k++) cur += '0';//乘积后面加上i个0 res = add(res, cur);//累加结果 } return res; }

string karatsuba(string a, string b) {//Karatsuba算法 int n = a.size(), m = b.size(); if(n < m) {//保证a的长度不小于b swap(a, b); swap(n, m); } if(n == 0 || m == 0) return "0"; if(n <= 50) return multiply(a, b);//当a的长度小于等于50时，直接使用高精度乘法 int k = (n + 1) / 2;//把a和b分别分成两半 string a1 = a.substr(0, k); string a2 = a.substr(k, n - k); string b1 = b.substr(0, min(m, k)); string b2 = b.substr(min(m, k), m - min(m, k)); string z0 = karatsuba(a2, b2);//计算z0 string z1 = karatsuba(add(a1, a2), add(b1, b2));//计算z1 string z2 = karatsuba(a1, b1);//计算z2 string p1 = sub(z1, add(z0, z2));//计算p1 string p2 = add(z2, multiply(p1, "10^" + to_string(2 * (n - k))));//计算p2 string p3 = add(p2, multiply(z0, "10^" + to_string(2 * k)));//计算p3 return p3;//返回p3 }

int main() { string a, b; cin >> a >> b; cout << karatsuba(a, b) << endl; return 0; }