{"id":1594,"date":"2026-05-19T16:28:23","date_gmt":"2026-05-19T08:28:23","guid":{"rendered":"http:\/\/wordpress.fangt.online\/?p=1594"},"modified":"2026-05-19T16:28:23","modified_gmt":"2026-05-19T08:28:23","slug":"%e9%ab%98%e7%b2%be%e5%ba%a6%e7%b1%bb%ef%bc%88%e9%9d%a2%e5%90%91%e5%af%b9%e8%b1%a1%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%e7%b1%bb%ef%bc%88%e9%9d%a2%e5%90%91%e5%af%b9%e8%b1%a1%ef%bc%89\/","title":{"rendered":"\u9ad8\u7cbe\u5ea6\u7c7b\uff08\u9762\u5411\u5bf9\u8c61\uff09"},"content":{"rendered":"\n
#include <iostream>\n#include <vector>\n#include <string>\n#include <algorithm>\n#include <cassert>\n\nclass BigInt {\nprivate:\n    std::vector<int> digits;  \/\/ \u5c0f\u7aef\u5e8f\u5b58\u50a8\uff0cdigits[0] \u662f\u4e2a\u4f4d\n    bool negative;            \/\/ true \u8868\u793a\u8d1f\u6570\uff0cfalse \u8868\u793a\u975e\u8d1f\u6570\n\n    \/\/ \u53bb\u9664\u524d\u5bfc\u96f6\uff08\u540c\u65f6\u5904\u7406\u7ed3\u679c\u4e3a 0 \u65f6\u7684\u7b26\u53f7\uff09\n    void trim() {\n        while (digits.size() > 1 && digits.back() == 0)\n            digits.pop_back();\n        if (digits.size() == 1 && digits[0] == 0)\n            negative = false;\n    }\n\n    \/\/ \u6bd4\u8f83\u7edd\u5bf9\u503c\u5927\u5c0f\uff08\u5c0f\u7aef\u5e8f\uff09\uff0c\u8fd4\u56de 1: |a|>|b|, 0: \u76f8\u7b49, -1: |a|<|b|\n    static int absCompare(const BigInt& a, const BigInt& b) {\n        if (a.digits.size() != b.digits.size())\n            return a.digits.size() > b.digits.size() ? 1 : -1;\n        for (int i = a.digits.size() - 1; i >= 0; --i) {\n            if (a.digits[i] != b.digits[i])\n                return a.digits[i] > b.digits[i] ? 1 : -1;\n        }\n        return 0;\n    }\n\n    \/\/ \u52a0\u6cd5\u6838\u5fc3\uff08\u7edd\u5bf9\u503c\u76f8\u52a0\uff09\uff0c\u7ed3\u679c\u4e3a\u6b63\n    static BigInt absAdd(const BigInt& a, const BigInt& b) {\n        BigInt res;\n        res.digits.clear();\n        int carry = 0;\n        size_t i = 0;\n        while (i < a.digits.size() || i < b.digits.size() || carry) {\n            int sum = carry;\n            if (i < a.digits.size()) sum += a.digits[i];\n            if (i < b.digits.size()) sum += b.digits[i];\n            res.digits.push_back(sum % 10);\n            carry = sum \/ 10;\n            ++i;\n        }\n        res.negative = false;\n        return res;\n    }\n\n    \/\/ \u51cf\u6cd5\u6838\u5fc3\uff08\u7edd\u5bf9\u503c\u76f8\u51cf\uff09\uff0c\u8981\u6c42 |a| >= |b|\uff0c\u7ed3\u679c\u4e3a\u6b63\n    static BigInt absSub(const BigInt& a, const BigInt& b) {\n        BigInt res;\n        res.digits.clear();\n        int borrow = 0;\n        for (size_t i = 0; i < a.digits.size(); ++i) {\n            int diff = a.digits[i] - borrow;\n            if (i < b.digits.size()) diff -= b.digits[i];\n            if (diff < 0) {\n                diff += 10;\n                borrow = 1;\n            } else {\n                borrow = 0;\n            }\n            res.digits.push_back(diff);\n        }\n        res.negative = false;\n        res.trim();\n        return res;\n    }\n\npublic:\n    \/\/ \u6784\u9020\u51fd\u6570\n    BigInt() : digits{0}, negative(false) {}\n    BigInt(long long num) : negative(false) {\n        if (num < 0) {\n            negative = true;\n            num = -num;\n        }\n        do {\n            digits.push_back(num % 10);\n            num \/= 10;\n        } while (num > 0);\n    }\n    BigInt(const std::string& s) {\n        if (s.empty()) {\n            digits.push_back(0);\n            negative = false;\n            return;\n        }\n        size_t start = 0;\n        negative = (s[0] == '-');\n        if (negative || s[0] == '+') start = 1;\n        for (int i = s.size() - 1; i >= (int)start; --i) {\n            digits.push_back(s[i] - '0');\n        }\n        trim();\n    }\n\n    \/\/ \u8f6c\u6362\u4e3a\u5b57\u7b26\u4e32\n    std::string toString() const {\n        if (digits.empty()) return \"0\";\n        std::string res;\n        if (negative) res += '-';\n        for (int i = digits.size() - 1; i >= 0; --i)\n            res += (digits[i] + '0');\n        return res;\n    }\n\n    \/\/ \u6bd4\u8f83\u8fd0\u7b97\u7b26\n    bool operator==(const BigInt& other) const {\n        return negative == other.negative && digits == other.digits;\n    }\n    bool operator!=(const BigInt& other) const { return !(*this == other); }\n    bool operator<(const BigInt& other) const {\n        if (negative != other.negative) return negative;\n        if (negative) {\n            \/\/ \u4e24\u4e2a\u8d1f\u6570\uff0c\u7edd\u5bf9\u503c\u5927\u7684\u53cd\u800c\u5c0f\n            int cmp = absCompare(*this, other);\n            return cmp == 1;\n        } else {\n            int cmp = absCompare(*this, other);\n            return cmp == -1;\n        }\n    }\n    bool operator>(const BigInt& other) const { return other < *this; }\n    bool operator<=(const BigInt& other) const { return !(*this > other); }\n    bool operator>=(const BigInt& other) const { return !(*this < other); }\n\n    \/\/ \u52a0\u51cf\u6cd5\n    BigInt operator+(const BigInt& other) const {\n        if (negative == other.negative) {\n            \/\/ \u540c\u53f7\u76f8\u52a0\uff1a\u7edd\u5bf9\u503c\u76f8\u52a0\uff0c\u7b26\u53f7\u4e0d\u53d8\n            BigInt res = absAdd(*this, other);\n            res.negative = negative;\n            return res;\n        } else {\n            \/\/ \u5f02\u53f7\u76f8\u52a0\uff1a\u76f8\u5f53\u4e8e\u7edd\u5bf9\u503c\u76f8\u51cf\uff0c\u7b26\u53f7\u7531\u7edd\u5bf9\u503c\u5927\u7684\u51b3\u5b9a\n            int cmp = absCompare(*this, other);\n            if (cmp == 0) return BigInt(0);\n            BigInt res;\n            if (cmp == 1) { \/\/ |this| > |other|\n                res = absSub(*this, other);\n                res.negative = negative; \/\/ \u7b26\u53f7\u4e0e\u7edd\u5bf9\u503c\u5927\u7684\u76f8\u540c\n            } else {\n                res = absSub(other, *this);\n                res.negative = other.negative;\n            }\n            return res;\n        }\n    }\n\n    BigInt operator-(const BigInt& other) const {\n        BigInt negOther = other;\n        negOther.negative = !negOther.negative;\n        return *this + negOther;\n    }\n\n    BigInt operator-() const {\n        BigInt res = *this;\n        if (res.digits.size() != 1 || res.digits[0] != 0)\n            res.negative = !res.negative;\n        return res;\n    }\n\n    \/\/ \u4e58\u6cd5\uff08\u666e\u901a O(n^2) \u7b97\u6cd5\uff0c\u53ef\u66ff\u6362\u4e3a Karatsuba\uff09\n    BigInt operator*(const BigInt& other) const {\n        BigInt res;\n        res.digits.assign(digits.size() + other.digits.size(), 0);\n        for (size_t i = 0; i < digits.size(); ++i) {\n            int carry = 0;\n            for (size_t j = 0; j < other.digits.size(); ++j) {\n                long long prod = (long long)digits[i] * other.digits[j] + res.digits[i + j] + carry;\n                res.digits[i + j] = prod % 10;\n                carry = prod \/ 10;\n            }\n            if (carry) {\n                res.digits[i + other.digits.size()] += carry;\n            }\n        }\n        res.negative = negative ^ other.negative;\n        res.trim();\n        return res;\n    }\n\n    \/\/ \u9664\u6cd5\uff08\u9ad8\u7cbe\u9664\u4ee5\u9ad8\u7cbe\uff0c\u8fd4\u56de\u5546\u548c\u4f59\u6570\uff09\n    friend std::pair<BigInt, BigInt> divmod(const BigInt& a, const BigInt& b);\n    BigInt operator\/(const BigInt& other) const {\n        return divmod(*this, other).first;\n    }\n    BigInt operator%(const BigInt& other) const {\n        return divmod(*this, other).second;\n    }\n\n    \/\/ \u590d\u5408\u8d4b\u503c\u8fd0\u7b97\u7b26\n    BigInt& operator+=(const BigInt& other) { *this = *this + other; return *this; }\n    BigInt& operator-=(const BigInt& other) { *this = *this - other; return *this; }\n    BigInt& operator*=(const BigInt& other) { *this = *this * other; return *this; }\n    BigInt& operator\/=(const BigInt& other) { *this = *this \/ other; return *this; }\n    BigInt& operator%=(const BigInt& other) { *this = *this % other; return *this; }\n\n    \/\/ \u8f93\u5165\u8f93\u51fa\n    friend std::ostream& operator<<(std::ostream& os, const BigInt& bi) {\n        os << bi.toString();\n        return os;\n    }\n    friend std::istream& operator>>(std::istream& is, BigInt& bi) {\n        std::string s;\n        is >> s;\n        bi = BigInt(s);\n        return is;\n    }\n};\n\n\/\/ \u9664\u6cd5\u8f85\u52a9\u51fd\u6570\uff08\u9ad8\u7cbe\u9664\u4ee5\u9ad8\u7cbe\uff0c\u4f7f\u7528\u7ad6\u5f0f\u8bd5\u5546\uff09\nstd::pair<BigInt, BigInt> divmod(const BigInt& a, const BigInt& b) {\n    if (b == BigInt(0)) throw std::runtime_error(\"Division by zero\");\n    if (a == BigInt(0)) return {BigInt(0), BigInt(0)};\n    \/\/ \u786e\u5b9a\u5546\u7684\u7b26\u53f7\n    bool resNegative = a.negative ^ b.negative;\n    \/\/ \u53d6\u7edd\u5bf9\u503c\u8fdb\u884c\u8ba1\u7b97\n    BigInt absA = a;\n    absA.negative = false;\n    BigInt absB = b;\n    absB.negative = false;\n\n    if (absA < absB) return {BigInt(0), a}; \/\/ \u5546\u4e3a0\uff0c\u4f59\u6570\u4e3aa\n\n    BigInt quotient;\n    BigInt remainder;\n    remainder.digits.clear();\n\n    \/\/ \u4ece\u88ab\u9664\u6570\u7684\u9ad8\u4f4d\u5f00\u59cb\u9010\u4f4d\u8bd5\u5546\n    for (int i = absA.digits.size() - 1; i >= 0; --i) {\n        \/\/ \u5c06\u5f53\u524d\u4f59\u6570\u5de6\u79fb\u4e00\u4f4d\uff08\u4e58\u4ee510\uff09\uff0c\u52a0\u4e0a\u88ab\u9664\u6570\u7684\u4e0b\u4e00\u4f4d\n        remainder.digits.insert(remainder.digits.begin(), absA.digits[i]);\n        remainder.trim();\n        \/\/ \u8bd5\u5546\uff1a\u5728 0-9 \u4e4b\u95f4\u627e\u5230\u6700\u5927\u7684 q \u4f7f\u5f97 q * absB <= remainder\n        int q = 0;\n        int left = 0, right = 9;\n        while (left <= right) {\n            int mid = (left + right) \/ 2;\n            BigInt prod = absB * BigInt(mid);\n            if (prod <= remainder) {\n                q = mid;\n                left = mid + 1;\n            } else {\n                right = mid - 1;\n            }\n        }\n        quotient.digits.push_back(q);\n        BigInt prod = absB * BigInt(q);\n        remainder = remainder - prod;\n        remainder.trim();\n    }\n    \/\/ \u6b64\u65f6 quotient.digits \u662f\u4ece\u9ad8\u4f4d\u5230\u4f4e\u4f4d\u5b58\u50a8\u7684\uff0c\u9700\u8981\u53cd\u8f6c\u6210\u5c0f\u7aef\u5e8f\n    std::reverse(quotient.digits.begin(), quotient.digits.end());\n    quotient.trim();\n    quotient.negative = resNegative;\n    remainder.negative = a.negative; \/\/ \u4f59\u6570\u7b26\u53f7\u4e0e\u88ab\u9664\u6570\u4e00\u81f4\n    return {quotient, remainder};\n}\n\n\/\/ \u793a\u4f8b\u7528\u6cd5\nint main() {\n    BigInt a(\"12345678901234567890\");\n    BigInt b(\"98765432109876543210\");\n    std::cout << \"a = \" << a << \"\\nb = \" << b << std::endl;\n    std::cout << \"a + b = \" << a + b << std::endl;\n    std::cout << \"a - b = \" << a - b << std::endl;\n    std::cout << \"a * b = \" << a * b << std::endl;\n    std::cout << \"a \/ b = \" << a \/ b << std::endl;\n    std::cout << \"a % b = \" << a % b << std::endl;\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","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-1594","post","type-post","status-publish","format-standard","hentry","category-zl"],"_links":{"self":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1594","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=1594"}],"version-history":[{"count":1,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1594\/revisions"}],"predecessor-version":[{"id":1595,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/posts\/1594\/revisions\/1595"}],"wp:attachment":[{"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/media?parent=1594"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/categories?post=1594"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/wordpress.fangt.online\/index.php\/wp-json\/wp\/v2\/tags?post=1594"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}