{"id":1591,"date":"2026-05-19T16:22:50","date_gmt":"2026-05-19T08:22:50","guid":{"rendered":"http:\/\/wordpress.fangt.online\/?p=1591"},"modified":"2026-05-19T16:22:50","modified_gmt":"2026-05-19T08:22:50","slug":"%e9%ab%98%e7%b2%be%e5%ba%a6%e4%b9%98%e6%b3%95%ef%bc%88karatsuba%ef%bc%89","status":"publish","type":"post","link":"http:\/\/wordpress.fangt.online\/index.php\/2026\/05\/19\/%e9%ab%98%e7%b2%be%e5%ba%a6%e4%b9%98%e6%b3%95%ef%bc%88karatsuba%ef%bc%89\/","title":{"rendered":"\u9ad8\u7cbe\u5ea6\u4e58\u6cd5\uff08Karatsuba\uff09"},"content":{"rendered":"\n

\u5bf9\u4e8e\u4e24\u4e2a n \u4f4d\u6570\u7684\u5927\u6574\u6570\uff0c\u666e\u901a\u7ad6\u5f0f\u4e58\u6cd5\uff08\u9010\u4f4d\u76f8\u4e58\u518d\u7d2f\u52a0\uff09\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f O(n\u00b2)<\/strong>\u3002\u5f53 n \u5f88\u5927\uff08\u6bd4\u5982\u4e0a\u4e07\u4f4d\uff09\u65f6\uff0c\u5e73\u65b9\u7ea7\u7684\u5f00\u9500\u4f1a\u975e\u5e38\u663e\u8457\u3002<\/p>\n\n\n\n

Karatsuba \u7b97\u6cd5<\/strong>\u00a0\u5229\u7528\u5206\u6cbb\u601d\u60f3\uff0c\u5c06\u65f6\u95f4\u590d\u6742\u5ea6\u964d\u5230\u00a0O(n^{log\u20823}) \u2248 O(n^{1.585})<\/strong>\uff0c\u662f\u7b2c\u4e00\u4e2a\u7a81\u7834 O(n\u00b2) \u7684\u5927\u6570\u4e58\u6cd5\u7b97\u6cd5\u3002<\/p>\n\n\n\n

\u6838\u5fc3\u601d\u60f3<\/h3>\n\n\n\n

\u8bbe\u6211\u4eec\u8981\u8ba1\u7b97\u4e24\u4e2a n \u4f4d\u6570 X<\/code> \u548c Y<\/code> \u7684\u4e58\u79ef\uff08\u5047\u8bbe n \u662f 2 \u7684\u5e42\uff0c\u4e0d\u8db3\u5219\u8865\u96f6\uff09\u3002<\/p>\n\n\n\n

\u5c06 X<\/code> \u548c Y<\/code> \u5404\u5206\u6210\u4e24\u534a\uff1a<\/p>\n\n\n\n

X = A * 10^{m} + B\nY = C * 10^{m} + D<\/code><\/pre>\n\n\n\n
\u5176\u4e2d m = n\/2<\/code>\uff0cA\u3001C \u662f\u9ad8\u534a\u90e8\u5206\uff0cB\u3001D \u662f\u4f4e\u534a\u90e8\u5206\u3002\u90a3\u4e48\uff1a<\/p>\n\n\n\n
X * Y = (A*10^m + B) * (C*10^m + D)\n      = AC * 10^{2m} + (AD + BC) * 10^{m} + BD<\/code><\/pre>\n\n\n\n
\u666e\u901a\u505a\u6cd5\u9700\u8981\u8ba1\u7b97\u56db\u6b21\u4e58\u6cd5\uff1aAC, AD, BC, BD\u3002Karatsuba \u89c2\u5bdf\u5230\uff1a<\/p>\n\n\n\n
AD + BC = (A+B)(C+D) - AC - BD<\/code><\/pre>\n\n\n\n
\u8fd9\u6837\u53ea\u9700\u8ba1\u7b97 \u4e09\u6b21\u4e58\u6cd5<\/strong>\uff1a<\/p>\n\n\n\n
    \n
  1. AC<\/code><\/li>\n\n\n\n
  2. BD<\/code><\/li>\n\n\n\n
  3. (A+B)(C+D)<\/code><\/li>\n<\/ol>\n\n\n\n
    \u7136\u540e\u7528\u52a0\u51cf\u6cd5\u7ec4\u5408\u51fa\u6700\u7ec8\u7ed3\u679c\u3002\u9012\u5f52\u5730\u5bf9\u8fd9\u4e09\u4e2a\u4e58\u79ef\u7ee7\u7eed\u4f7f\u7528 Karatsuba \u65b9\u6cd5\uff0c\u76f4\u5230\u6570\u5b57\u8db3\u591f\u5c0f\uff08\u4f8b\u5982 32 \u4f4d\u4ee5\u5185\uff09\u6539\u7528\u76f4\u63a5\u4e58\u6cd5\u3002<\/p>\n\n\n\n
    \u7b97\u6cd5\u6b65\u9aa4<\/h3>\n\n\n\n
      \n
    1. \u8f93\u5165\u4e24\u4e2a\u5927\u6570\u00a0X<\/code>\u00a0\u548c\u00a0Y<\/code>\uff08\u5b57\u7b26\u4e32\u6216\u5c0f\u7aef\u5e8f\u6570\u7ec4\uff09\u3002<\/li>\n\n\n\n
    2. \u82e5\u957f\u5ea6\u5c0f\u4e8e\u67d0\u9608\u503c\uff08\u5982 32 \u6216 64\uff09\uff0c\u76f4\u63a5\u7528\u666e\u901a\u4e58\u6cd5\u8fd4\u56de\u3002<\/li>\n\n\n\n
    3. \u5c06\u00a0X<\/code>\u00a0\u548c\u00a0Y<\/code>\u00a0\u8865\u9f50\u5230\u76f8\u540c\u957f\u5ea6\uff0c\u4e14\u957f\u5ea6\u4e3a 2 \u7684\u5e42\uff08\u65b9\u4fbf\u5206\u534a\uff09\u3002<\/li>\n\n\n\n
    4. \u53d6\u5206\u5272\u70b9\u00a0m = n\/2<\/code>\uff0c\u5f97\u5230 A\u3001B\u3001C\u3001D\u3002<\/li>\n\n\n\n
    5. \u9012\u5f52\u8ba1\u7b97\uff1a\n
        \n
      • z0 = karatsuba(A, C)<\/code><\/li>\n\n\n\n
      • z2 = karatsuba(B, D)<\/code><\/li>\n\n\n\n
      • z1 = karatsuba(A+B, C+D) - z0 - z2<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • \u5408\u5e76\u7ed3\u679c\uff1az0 * 10^{2m} + z1 * 10^{m} + z2<\/code>\u3002<\/li>\n\n\n\n
      • \u5904\u7406\u8fdb\u4f4d\u5e76\u8fd4\u56de\u3002<\/li>\n<\/ol>\n\n\n\n
        \u4ee3\u7801\u5b9e\u73b0<\/h3>\n\n\n\n
        #include <iostream>\n#include <vector>\n#include <string>\n#include <algorithm>\n#include <cmath>\n\nusing namespace std;\n\nusing BigInt = vector<int>;\n\n\/\/ \u666e\u901a\u9ad8\u7cbe\u5ea6\u4e58\u6cd5\uff08O(n^2)\uff09\uff0c\u7528\u4e8e\u5c0f\u89c4\u6a21\u9012\u5f52\u57fa\u7840\u60c5\u51b5\nBigInt mulBrute(const BigInt& a, const BigInt& b) {\n    BigInt c(a.size() + b.size(), 0);\n    for (size_t i = 0; i < a.size(); ++i) {\n        long long carry = 0;\n        for (size_t j = 0; j < b.size(); ++j) {\n            long long cur = c[i + j] + (long long)a[i] * b[j] + carry;\n            c[i + j] = cur % 10;\n            carry = cur \/ 10;\n        }\n        if (carry) c[i + b.size()] += carry; \/\/ \u6ce8\u610f\u53ef\u80fd\u8d85\u8fc7\u4e00\u4f4d\uff0c\u4f46\u8fdb\u4f4d\u6700\u591a\u4e00\u4f4d\n    }\n    while (c.size() > 1 && c.back() == 0) c.pop_back();\n    return c;\n}\n\n\/\/ \u8f85\u52a9\u51fd\u6570\uff1a\u4e24\u4e2a\u5927\u6570\u76f8\u52a0\uff08\u5c0f\u7aef\u5e8f\uff09\nBigInt add(const BigInt& a, const BigInt& b) {\n    BigInt c;\n    int carry = 0;\n    size_t i = 0;\n    while (i < a.size() || i < b.size() || carry) {\n        int sum = carry;\n        if (i < a.size()) sum += a[i];\n        if (i < b.size()) sum += b[i];\n        c.push_back(sum % 10);\n        carry = sum \/ 10;\n        ++i;\n    }\n    return c;\n}\n\n\/\/ \u8f85\u52a9\u51fd\u6570\uff1a\u4e24\u4e2a\u5927\u6570\u76f8\u51cf\uff08\u8981\u6c42 a >= b\uff09\nBigInt sub(const BigInt& a, const BigInt& b) {\n    BigInt c;\n    int borrow = 0;\n    for (size_t i = 0; i < a.size(); ++i) {\n        int diff = a[i] - borrow;\n        if (i < b.size()) diff -= b[i];\n        if (diff < 0) {\n            diff += 10;\n            borrow = 1;\n        } else {\n            borrow = 0;\n        }\n        c.push_back(diff);\n    }\n    while (c.size() > 1 && c.back() == 0) c.pop_back();\n    return c;\n}\n\n\/\/ \u5927\u6570\u5de6\u79fb\uff08\u4e58\u4ee5 10^k\uff09\uff0c\u5373\u5728\u4f4e\u4f4d\u8865 k \u4e2a 0\nBigInt shiftLeft(const BigInt& a, int k) {\n    if (a.size() == 1 && a[0] == 0) return a;\n    BigInt res(k, 0); \/\/ \u4f4e\u4f4d\u8865\u96f6\n    res.insert(res.end(), a.begin(), a.end());\n    return res;\n}\n\n\/\/ Karatsuba \u4e58\u6cd5\nBigInt karatsuba(const BigInt& a, const BigInt& b) {\n    \/\/ \u57fa\u7840\u60c5\u51b5\uff1a\u4f7f\u7528\u666e\u901a\u4e58\u6cd5\n    const int THRESHOLD = 64; \/\/ \u7ecf\u9a8c\u503c\uff0c\u53ef\u8c03\u8282\n    if (a.size() < THRESHOLD || b.size() < THRESHOLD) {\n        return mulBrute(a, b);\n    }\n\n    \/\/ \u786e\u4fdd\u4e24\u6570\u957f\u5ea6\u4e00\u81f4\uff0c\u5e76\u53d6\u6700\u5927\u957f\u5ea6\n    size_t n = max(a.size(), b.size());\n    \/\/ \u5411\u4e0a\u53d6\u6574\u4e3a\u5076\u6570\uff0c\u65b9\u4fbf\u5206\u534a\uff08\u4e5f\u53ef\u53d6 n\/2 \u5411\u4e0a\u53d6\u6574\uff09\n    if (n % 2 != 0) ++n;\n    BigInt a2 = a, b2 = b;\n    a2.resize(n, 0);\n    b2.resize(n, 0);\n\n    size_t m = n \/ 2; \/\/ \u5206\u5272\u70b9\uff08\u4f4e\u4f4d\u90e8\u5206\u957f\u5ea6\uff09\n    \/\/ \u5206\u5272: A = \u9ad8\u4f4d\u90e8\u5206 (a2[m..n-1]), B = \u4f4e\u4f4d\u90e8\u5206 (a2[0..m-1])\n    BigInt lowA(a2.begin(), a2.begin() + m);\n    BigInt highA(a2.begin() + m, a2.end());\n    BigInt lowB(b2.begin(), b2.begin() + m);\n    BigInt highB(b2.begin() + m, b2.end());\n\n    \/\/ \u9012\u5f52\u8ba1\u7b97\u4e09\u4e2a\u4e58\u79ef\n    BigInt z0 = karatsuba(highA, highB);          \/\/ AC\n    BigInt z2 = karatsuba(lowA, lowB);            \/\/ BD\n    BigInt sumA = add(highA, lowA);               \/\/ A+B\n    BigInt sumB = add(highB, lowB);               \/\/ C+D\n    BigInt z1 = karatsuba(sumA, sumB);            \/\/ (A+B)(C+D)\n    z1 = sub(z1, z0);\n    z1 = sub(z1, z2);                             \/\/ (A+B)(C+D) - AC - BD\n\n    \/\/ \u7ec4\u5408\u7ed3\u679c: z0 * 10^{2m} + z1 * 10^{m} + z2\n    BigInt result = add(z2, shiftLeft(z1, m));\n    result = add(result, shiftLeft(z0, 2 * m));\n\n    \/\/ \u53bb\u9664\u524d\u5bfc\u96f6\n    while (result.size() > 1 && result.back() == 0)\n        result.pop_back();\n    return result;\n}\n\n\/\/ \u5b57\u7b26\u4e32\u8f6c\u5c0f\u7aef\u5e8f\nBigInt strToVec(const string& s) {\n    BigInt v;\n    for (int i = s.size() - 1; i >= 0; --i)\n        v.push_back(s[i] - '0');\n    return v;\n}\n\n\/\/ \u8f93\u51fa\u5c0f\u7aef\u5e8f\nvoid printVec(const BigInt& v) {\n    for (int i = v.size() - 1; i >= 0; --i)\n        cout << v[i];\n    cout << endl;\n}\n\nint main() {\n    string s1, s2;\n    cin >> s1 >> s2;\n    BigInt a = strToVec(s1);\n    BigInt b = strToVec(s2);\n    BigInt c = karatsuba(a, b);\n    printVec(c);\n    return 0;\n}<\/code><\/pre>\n\n\n\n
        \u590d\u6742\u5ea6\u5206\u6790<\/h3>\n\n\n\n
          \n
        • \u65f6\u95f4\u590d\u6742\u5ea6<\/strong>\uff1a\u9012\u63a8\u5f0f\u00a0T(n) = 3T(n\/2) + O(n)<\/code>\uff0c\u89e3\u5f97\u00a0T(n) = O(n^{log\u20823}) \u2248 O(n^{1.585})<\/code>\u3002<\/li>\n\n\n\n
        • \u7a7a\u95f4\u590d\u6742\u5ea6<\/strong>\uff1a\u9012\u5f52\u6808\u6df1\u5ea6 O(log n)\uff0c\u6bcf\u5c42\u9700\u8981\u5b58\u50a8\u4e2d\u95f4\u7ed3\u679c\uff0c\u603b\u7a7a\u95f4 O(n)\u3002<\/li>\n<\/ul>\n\n\n\n
          <\/p>\n","protected":false},"excerpt":{"rendered":"
          \u5bf9\u4e8e\u4e24\u4e2a n \u4f4d\u6570\u7684\u5927\u6574\u6570\uff0c\u666e\u901a\u7ad6\u5f0f\u4e58\u6cd5\uff08\u9010\u4f4d\u76f8\u4e58\u518d\u7d2f\u52a0\uff09\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f O(n\u00b2)\u3002\u5f53 n \u5f88\u5927\uff08 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[61],"tags":[],"class_list":["post-1591","post","type-post","status-publish","format-standard","hentry","category-zl"],"_links":{"self":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1591","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/comments?post=1591"}],"version-history":[{"count":1,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1591\/revisions"}],"predecessor-version":[{"id":1592,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1591\/revisions\/1592"}],"wp:attachment":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/media?parent=1591"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/categories?post=1591"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/tags?post=1591"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}