{"id":420,"date":"2022-12-26T01:18:59","date_gmt":"2022-12-25T17:18:59","guid":{"rendered":"https:\/\/blog.cirno.fun\/?p=420"},"modified":"2024-09-12T09:30:26","modified_gmt":"2024-09-12T01:30:26","slug":"%e8%a3%b4%e8%9c%80%e5%ae%9a%e7%90%86%e4%b8%8e%e6%89%a9%e5%b1%95%e6%ac%a7%e5%87%a0%e9%87%8c%e5%be%97%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=420","title":{"rendered":"\u88f4\u8700\u5b9a\u7406\u4e0e\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5"},"content":{"rendered":"<p>\u88f4\u8700\u5b9a\u7406\uff1a \u5bf9\u4e8e\u4e00\u5bf9\u6b63\u6574\u6570a,b,\u7531\u4f59\u6570\u7684\u6027\u8d28\uff0c\u663e\u7136<\/p>\n<pre><code class=\"language-katex\">\\forall x,y \\in Z,\u6709 gcd(a,b) \\mid ax+by\\\\\n\u5373a,b\u7684\u7ebf\u6027\u7ec4\u5408\u603b\u88ab\u6700\u5927\u516c\u7ea6\u6570d\u6574\u9664<\/code><\/pre>\n<p>\u800c\u7279\u522b\u7684<\/p>\n<pre><code class=\"language-katex\">\\exists  x,y \\in Z,\u4ee4 gcd(a,b) = ax+by<\/code><\/pre>\n<p>\u4f8b\u5982<\/p>\n<pre><code class=\"language-katex\">a=15,b=25\\\\d=gcd(a,b)=5\\\\\u800cd = 2a-b<\/code><\/pre>\n<p>\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u4fbf\u662f\u6c42\u5f97\u5728\u2461\u5f0f\u4e2dx,y\u7684\u503c\u7684\u6709\u6548\u65b9\u6cd5<\/p>\n<p>\u590d\u4e60\u4e00\u4e0b\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff08\u8f97\u8f6c\u76f8\u9664\u6cd5\uff09<\/p>\n<pre><code class=\"language-cpp\">int gcd(int a, int b)\n{\n    return b ? gcd(b, a % b) : a;\n}<\/code><\/pre>\n<p>\u8fd9\u91cc\u7ed9\u51fa\u4e00\u4e2a\u63a8\u5bfc\u8fc7\u7a0b<\/p>\n<pre><code class=\"language-katex\">\u4ee4d=gcd(a,b)=gcd(b,a\\%b) \\\\\nax+by=d\\\\\nbx_1+(a\\%b)y_1=d\\\\\n\u8054\u7acb\u6709ax+by=bx_1+(a\\%b)y_1\\\\\n\u53c8a\\%b=a-[\\frac{a}{b}]b\\\\\n\u6574\u7406\u7cfb\u6570\u53ef\u5f97\\\\\n\\begin{cases}\n  &amp; x=y_1 \\\\\n  &amp; y=x_1-[\\frac{b}{a}]y_1\\\\\n\\end{cases}\\\\<\/code><\/pre>\n<p>\u89c2\u5bdf\u7ed3\u8bba\uff0c\u4e0d\u96be\u53d1\u73b0x1\uff0cy1\u7684\u89c4\u6a21\u8981\u6bd4xy\u672c\u8eab\u8981\u5c0f\uff0c\u6240\u4ee5\u53ef\u4ee5\u9012\u5f52\u89e3\u51b3\u8be5\u95ee\u9898<\/p>\n<p>\u540c\u6837\u7684\uff0c\u5728\u9012\u5f52\u51fa\u53e3b==0\u65f6\uff0c\u8fd4\u56degcd=a\uff0c\u5bf9\u4e8e\u8be5\u5c40\u90e8\u95ee\u9898\uff0c\u6709x=1,y=0 \u56e0\u4e3a<code>gcd=a=1a+0b<\/code><\/p>\n<p>\u7efc\u4e0a\u53ef\u4ee5\u5199\u51fa\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u7684\u5b8c\u6574\u4ee3\u7801<\/p>\n<pre><code class=\"language-cpp\">\/\/xy\u7684\u503c\u4ee5\u5f15\u7528\u7684\u65b9\u6cd5\u4f20\u56de\nint exgcd(int a, int b, int &amp;x, int &amp;y)\n{\n    if(!b)\n    {\n        x = 1; y = 0;\n        return a;\n    }\n    int res = exgcd(b, a % b, y, x);\n    y -= (a \/ b) * x;\n    return res;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u88f4\u8700\u5b9a\u7406\uff1a \u5bf9\u4e8e\u4e00\u5bf9\u6b63\u6574\u6570a,b,\u7531\u4f59\u6570\u7684\u6027\u8d28\uff0c\u663e\u7136 \\forall x,y \\ [&#8230;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,16],"tags":[],"class_list":["post-420","post","type-post","status-publish","format-standard","hentry","category-13","category-16"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/420","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=420"}],"version-history":[{"count":1,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/420\/revisions"}],"predecessor-version":[{"id":734,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/420\/revisions\/734"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=420"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=420"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=420"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}