{"id":825,"date":"2026-03-05T10:52:33","date_gmt":"2026-03-05T02:52:33","guid":{"rendered":"https:\/\/vite66.cn\/?p=825"},"modified":"2026-03-05T11:11:37","modified_gmt":"2026-03-05T03:11:37","slug":"%e6%ac%a7%e5%87%a0%e9%87%8c%e5%be%97%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/vite66.cn\/?p=825","title":{"rendered":"\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5"},"content":{"rendered":"

\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u4e0e\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff1a\u539f\u7406\u3001\u8bc1\u660e\u53ca\u5b9e\u73b0<\/h1>\n

1 \u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5<\/h2>\n

1.1 \u5b9a\u4e49\u4e0e\u57fa\u672c\u7b26\u53f7<\/h3>\n

\u8bbe $a, b$ \u4e3a\u4e0d\u5168\u4e3a0\u7684\u6b63\u6574\u6570\uff0c $\\gcd(a, b)$ \u8868\u793a $a$ \u4e0e $b$ \u7684\u6700\u5927\u516c\u7ea6\u6570<\/strong>\u3002<\/p>\n

\u5bf9 $a, b$ \u505a\u5e26\u4f59\u9664\u6cd5\uff1a<\/p>\n

$a = q\\cdot b + r,\\quad 0\\le r < b$ <\/p>\n

\u5176\u4e2d $q = \\lfloor \\frac{a}{b} \\rfloor$ \u4e3a\u5546\uff0c $r = a \\bmod b$ \u4e3a\u4f59\u6570\u3002<\/p>\n

1.2 \u6838\u5fc3\u5f15\u7406<\/h3>\n

$\\gcd(a, b) = \\gcd(b, a \\bmod b)$ <\/p>\n

1.3 \u4e25\u683c\u8bc1\u660e<\/h3>\n

\u8bc1\u660e\u601d\u8def<\/strong>\uff1a\u8bc1\u660e $a,b$ \u4e0e $b,r$ \u7684\u516c\u7ea6\u6570\u96c6\u5408\u5b8c\u5168\u76f8\u7b49\uff0c\u5219\u5176\u6700\u5927\u5143\u7d20\u76f8\u7b49\u3002<\/p>\n

\u8bbe $d$ \u4e3a $a,b$ \u7684\u4efb\u610f\u516c\u7ea6\u6570\uff0c\u5373 $d\\mid a$ \u4e14 $d\\mid b$ \u3002<\/p>\n

\u7531\u6574\u9664\u7684\u7ebf\u6027\u6027\u8d28\uff1a\u82e5 $d\\mid m$ \u4e14 $d\\mid n$ \uff0c\u5219\u5bf9\u4efb\u610f\u6574\u6570 $k,l$ \u6709 $d\\mid (km+ln)$ \u3002<\/p>\n

\u7531 $r = a - qb$ \uff0c\u5f97 $d\\mid r$ \uff0c\u6545 $d$ \u4e3a $b,r$ \u7684\u516c\u7ea6\u6570\u3002<\/p>\n

\u53cd\u4e4b\uff0c\u8bbe $d$ \u4e3a $b,r$ \u7684\u4efb\u610f\u516c\u7ea6\u6570\uff0c\u5373 $d\\mid b$ \u4e14 $d\\mid r$ \u3002<\/p>\n

\u7531 $a = qb + r$ \uff0c\u5f97 $d\\mid a$ \uff0c\u6545 $d$ \u4e3a $a,b$ \u7684\u516c\u7ea6\u6570\u3002<\/p>\n

\u56e0\u6b64\uff1a<\/p>\n

${d\\mid d\\mid a \\land d\\mid b} = {d\\mid d\\mid b \\land d\\mid r}$ <\/p>\n

\u4e24\u96c6\u5408\u6700\u5927\u5143\u7d20\u76f8\u7b49\uff0c\u5373 $\\gcd(a,b)=\\gcd(b,a\\bmod b)$ \u3002<\/p>\n

1.4 \u7b97\u6cd5\u7ec8\u6b62\u6761\u4ef6<\/h3>\n

\u5f53 $b=0$ \u65f6\uff0c $\\gcd(a,0)=a$ \uff0c\u6b64\u65f6 $a$ \u5373\u4e3a\u6700\u5927\u516c\u7ea6\u6570\u3002<\/p>\n

1.5 \u7b97\u6cd5\u5b9e\u73b0\uff08C++\uff09<\/h3>\n
\n\/\/ \u9012\u5f52\u5b9e\u73b0\nint gcd(int a, int b) {\n    return b == 0 ? a : gcd(b, a % b);\n}\n\n\/\/ \u8fed\u4ee3\u5b9e\u73b0\nint gcd_iter(int a, int b) {\n    while (b != 0) {\n        int r = a % b;\n        a = b;\n        b = r;\n    }\n    return a;\n}<\/code><\/pre>\n
2 \u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5<\/h2>\n
2.1 \u6570\u5b66\u57fa\u7840\uff1a\u8d1d\u7956\u5b9a\u7406<\/h3>\n
\u5bf9\u4efb\u610f\u4e0d\u5168\u4e3a0\u7684\u6574\u6570  $a,b$ \uff0c\u5b58\u5728\u6574\u6570 <\/strong> $x,y$  \u4f7f\u5f97\uff1a<\/p>\n
$ax + by = \\gcd(a,b)$ <\/p>\n
\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u5728\u6c42\u89e3  $\\gcd(a,b)$  \u7684\u540c\u65f6\uff0c\u53ef\u6c42\u51fa\u4e00\u7ec4\u6574\u6570\u89e3  $(x,y)$ \u3002<\/p>\n
2.2 \u9012\u63a8\u5173\u7cfb\u63a8\u5bfc<\/h3>\n
\u8bbe\uff1a<\/p>\n
$ax_1 + by_1 = \\gcd(a,b)$ <\/p>\n
\u4ee4  $r=a\\bmod b$ \uff0c\u7531\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff1a<\/p>\n
$bx_2 + ry_2 = \\gcd(b,r) = \\gcd(a,b)$ <\/p>\n
\u5c06  $r = a - \\lfloor \\frac{a}{b} \\rfloor \\cdot b$  \u4ee3\u5165\u4e0a\u5f0f\uff1a<\/p>\n
$bx_2 + (a - \\lfloor \\tfrac{a}{b} \\rfloor \\cdot b)y_2 = \\gcd(a,b)$ <\/p>\n
\u6574\u7406\u5f97\uff1a<\/p>\n
$a\\cdot y_2 + b\\cdot (x_2 - \\lfloor \\tfrac{a}{b} \\rfloor y_2) = \\gcd(a,b)$<\/p>\n
\u5bf9\u6bd4\u7cfb\u6570\u53ef\u5f97\u9012\u63a8\u516c\u5f0f\uff1a
\n$\\begin{cases}x_1 = y_2 \\\\ y_1 = x_2 - \\lfloor \\tfrac{a}{b} \\rfloor \\cdot y_2 \\end{cases}$<\/p>\n
2.3 \u9012\u5f52\u7ec8\u6b62\u6761\u4ef6<\/h3>\n
\u5f53  $b=0$  \u65f6\uff0c $\\gcd(a,0)=a$ \uff0c\u65b9\u7a0b  $a\\cdot1 + 0\\cdot0 = a$  \u6210\u7acb\uff0c\u5373\uff1a<\/p>\n
$x=1,\\ y=0$ <\/p>\n
2.4 \u7b97\u6cd5\u5b9e\u73b0\uff08C++\uff09<\/h3>\n
\n\/\/ \u8fd4\u56degcd(a,b)\uff0cx\u3001y\u4e3a\u5f15\u7528\u4f20\u53c2\uff0c\u5b58\u50a8\u65b9\u7a0b\u89e3\nint exgcd(int a, int b, int &x, int &y) {\n    if (b == 0) {\n        x = 1, y = 0;\n        return a;\n    }\n    int g = exgcd(b, a % b, y, x);\n    y -= a \/ b * x;\n    return g;\n}<\/code><\/pre>\n
3 \u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u4e0e\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u7684\u5173\u8054<\/h2>\n
    \n
  1. \n
    \u4e8c\u8005\u5171\u7528\u540c\u4e00\u8f97\u8f6c\u76f8\u9664\u6846\u67b6<\/strong>\uff0c\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u662f\u5bf9\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u7684\u76f4\u63a5\u6269\u5c55\uff1b<\/p>\n<\/li>\n
  2. \n
    \u6b27\u51e0\u91cc\u5f97\u4ec5\u6c42\u89e3\u6700\u5927\u516c\u7ea6\u6570\uff0c\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u989d\u5916\u6c42\u89e3\u8d1d\u7956\u65b9\u7a0b\u7684\u6574\u6570\u89e3\uff1b<\/p>\n<\/li>\n
  3. \n
    \u65f6\u95f4\u590d\u6742\u5ea6\u4e00\u81f4\uff0c\u5747\u4e3a  $O(\\log\\min(a,b))$ \uff1b<\/p>\n<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
    \u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u4e0e\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff1a\u539f\u7406\u3001\u8bc1\u660e\u53ca\u5b9e\u73b0 1 \u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5 1.1 \u5b9a\u4e49\u4e0e\u57fa\u672c\u7b26\u53f7 \u8bbe $a, b$  […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-825","post","type-post","status-publish","format-standard","hentry","category-science-and-engineering"],"_links":{"self":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/825","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=825"}],"version-history":[{"count":12,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/825\/revisions"}],"predecessor-version":[{"id":837,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/825\/revisions\/837"}],"wp:attachment":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=825"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=825"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=825"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}