{"id":375,"date":"2023-05-04T18:26:14","date_gmt":"2023-05-04T10:26:14","guid":{"rendered":"https:\/\/www.xgnd.net\/?p=375"},"modified":"2025-11-22T12:43:29","modified_gmt":"2025-11-22T04:43:29","slug":"%e3%80%8c%e5%ad%a6%e4%b9%a0%e7%ac%94%e8%ae%b0%e3%80%8d%e4%b8%ad%e5%9b%bd%e5%89%a9%e4%bd%99%e5%ae%9a%e7%90%86","status":"publish","type":"post","link":"https:\/\/www.xgnd.net\/index.php\/2023\/05\/04\/%e3%80%8c%e5%ad%a6%e4%b9%a0%e7%ac%94%e8%ae%b0%e3%80%8d%e4%b8%ad%e5%9b%bd%e5%89%a9%e4%bd%99%e5%ae%9a%e7%90%86\/","title":{"rendered":"\u300c\u5b66\u4e60\u7b14\u8bb0\u300d\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406"},"content":{"rendered":"<h2>\u5b9a\u4e49<\/h2>\n<p>\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\uff08Chinese Remainder Theorem\uff0cCRT\uff09\uff0c\u53ef\u7528\u4e8e\u6c42\u89e3\u5982\u4e0b\u5f62\u5f0f\u7684\u4e00\u5143\u7ebf\u6027\u540c\u4f59\u65b9\u7a0b\u7ec4\uff08\u5176\u4e2d $a_1,a_2,...,a_3$ \u4e24\u4e24\u4e92\u8d28 \uff09\uff1a<\/p>\n<p>$\\begin{cases} x \\equiv a_1\\ ({\\rm mod}\\ n_1) \\ x\\equiv a_2\\ ({\\rm mod}\\ n_2) \\ ... \\ x \\equiv a_k\\ ({\\rm mod}\\ n_k)\\end{cases}$<\/p>\n<h2>\u89e3\u6cd5<\/h2>\n<ul>\n<li>\n<p>\u5148\u6c42\u51fa\u6a21\u6570\u7684\u79ef $N$ \uff0c\u8bbe $N=\\prod_{i=1}^k n_i$  <\/p>\n<\/li>\n<li>\n<p>\u5bf9\u4e8e\u7b2c $i$ \u4e2a\u65b9\u7a0b\uff1a<\/p>\n<ul>\n<li>\u5148\u6c42\u9664\u4e86 $n_i$ \u5916\u7684\u6240\u6709\u6a21\u6570\u4e4b\u79ef\uff0c\u8bbe $N_i=\\frac{N}{n_i}$ <\/li>\n<li>\u6c42 $N_i$ \u5728\u6a21 $n_i$ \u610f\u4e49\u4e0b\u7684\u9006\u5143 $N_i^{-1}$ \uff0c\u5373 $N_i\\times N_i^{-1} \\equiv 1\\ ({\\rm mod}\\ n_i)$<\/li>\n<\/ul>\n<\/li>\n<li>\n<p>\u6700\u5c0f\u6b63\u6574\u6570\u89e3 $x=\\sum_{i=1}^k a_i\\times N_i\\times N_i^{-1}$ <\/p>\n<\/li>\n<\/ul>\n<h2>\u8bc1\u660e<\/h2>\n<p>\u5bf9\u4e8e\u7b2c $i$ \u4e2a\u65b9\u7a0b\uff1a<\/p>\n<ul>\n<li>\u5f53 $i\\not = j$ \u65f6\uff0c\u6709 $a_j\\times N_j\\times N_j^{-1} \\equiv 0\\ ({\\rm mod}\\ n_i)$ \uff0c\u56e0\u4e3a $N_j$ \u4e2d\u5fc5\u7136\u6709 $n_i$ \u3002<\/li>\n<li>\u5f53 $i=j$ \u65f6\uff0c\u6709 $a_i\\times N_i\\times N_i^{-1} \\equiv a_i\\ ({\\rm mod}\\ n_i)$ \u3002<\/li>\n<\/ul>\n<p>\u56e0\u6b64\uff0c$\\sum_{i=1}^k a_i\\times N_i\\times N_i^{-1}\\equiv a_i\\ ({\\rm mod}\\ n_i)$ \u3002<\/p>\n<h2>\u5b9e\u73b0<\/h2>\n<pre><code class=\"language-c++\">ll CRT() {\n    ll s = 1, ans = 0;\n    for (int i = 1; i &amp;lt;= n; i++)s *= b[i];\n    for (int i = 1; i &amp;lt;= n; i++) {\n        ll x, y, r = s \/ b[i];\n        exgcd(r, b[i], x, y);   \/\/\u6c42\u9006\u5143\n        (ans += c[i] * r * x) %= s;\n    }\n    return (ans % s + s) % s;\n}<\/code><\/pre>\n<h1>\u6269\u5c55\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406<\/h1>\n<h2>\u5b9a\u4e49<\/h2>\n<p>$\\begin{cases} x \\equiv a_1\\ ({\\rm mod}\\ n_1) \\ x\\equiv a_2\\ ({\\rm mod}\\ n_2) \\ ... \\ x \\equiv a_k\\ ({\\rm mod}\\ n_k)\\end{cases}$<\/p>\n<p>\u4ecd\u7136\u662f\u8fd9\u4e2a\u65b9\u7a0b\u7ec4\uff0c\u4f46\u6b64\u65f6\u6a21\u6570\u4e0d\u4e92\u8d28\u4e86\u3002<\/p>\n<h2>\u89e3\u6cd5\u548c\u8bc1\u660e<\/h2>\n<p>\u7531\u4e8e\u6a21\u6570\u4e0d\u4e92\u8d28\uff0c$N_i$ \u4e0e $n_i$ \u4e5f\u4e0d\u4e92\u8d28\uff0c\u5219\u4e0d\u5b58\u5728 $N_i$ \u7684\u9006\u5143\u3002\u6b64\u65f6\u518d\u7528\u539f\u7b97\u6cd5\u7b97\u5c31\u4e0d\u5bf9\u4e86\u3002<\/p>\n<p>\u4e8e\u662f\u53ef\u4ee5\u8003\u8651\u6362\u4e00\u79cd\u65b9\u6cd5\uff0c\u57fa\u672c\u60f3\u6cd5\u5c31\u662f\u8003\u8651\u5c06\u4e24\u4e2a\u540c\u4f59\u65b9\u7a0b\u5408\u5e76\u4e3a\u4e00\u4e2a\uff0c\u4f9d\u6b21\u6c42\u89e3\u3002<\/p>\n<p>$$\\begin{cases} x \\equiv a_1\\ ({\\rm mod}\\ n_1) \\ x\\equiv a_2\\ ({\\rm mod}\\ n_2) \\ \\end{cases}$$<\/p>\n<p>\u5bf9\u4e8e\u8fd9\u4e24\u4e2a\u65b9\u7a0b\uff0c\u6211\u4eec\u53ef\u4ee5\u628a\u5b83\u5199\u6210\uff1a<\/p>\n<p>$$ x=k_1 n_1+a_1=k_2 n_2+a_2 $$<\/p>\n<p>\u79fb\u9879\u4e00\u4e0b\uff0c\u6709\uff1a<\/p>\n<p>$$ k_1n_1-k_2n_2=a_2-a_1 $$<\/p>\n<p>\u53ef\u4ee5\u53d1\u73b0\uff0c\u5f0f\u5b50\u4e2d\u53ea\u6709 $k_1,k_2$ \u4e24\u4e2a\u672a\u77e5\u6570\uff0c\u53ef\u4ee5\u7528\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u6c42\u51fa $k_1,k_2$ \u4e00\u7ec4\u89e3\uff1a<\/p>\n<p>\u8bbe $g=gcd(n_1,n_2)$ \uff0c$k_1',k_2'$ \u4e3a exgcd \u6c42\u51fa\u7684\u503c\u3002<\/p>\n<p>$$\\begin{cases} k_1=\\frac{k_1'(a_2-a_1)}{g} \\ k_2=\\frac{k_2'(a_2-a_1)}{g}\\ \\end{cases}$$<\/p>\n<p>\u4ee3\u56de\u539f\u5f0f\u5373\u53ef\u5f97\u5230\u65b9\u7a0b\u7ec4\u7684\u4e00\u7ec4\u7279\u89e3\uff1a<\/p>\n<p>$$x_0=\\frac{k_1'(a_2-a_1)}{g}n_1+a_1$$<\/p>\n<p>\u800c\u65b9\u7a0b\u7ec4\u7684\u901a\u89e3\u5373\u4e3a\uff1a<\/p>\n<p>$$x=x_0\\ \\pm\\ K\\cdot lcm(n_1\\ ,\\ n_2)$$<\/p>\n<p>\u8fd9\u4e2a\u5f0f\u5b50\u53c8\u7b49\u4ef7\u4e8e\u8fd9\u6837\u4e00\u4e2a\u65b0\u7684\u65b9\u7a0b\uff1a<\/p>\n<p>$$x\\equiv x_0\\ ({\\rm mod}\\ lcm(n_1,n_2)) $$<\/p>\n<p>\u8fd9\u6837\u6211\u4eec\u5c31\u6210\u529f\u628a\u4e24\u4e2a\u65b9\u7a0b\u5408\u5e76\u4e3a\u4e00\u4e2a\u4e86\u3002<\/p>\n<p>\u4e3b\u8981\u601d\u8def\u5c31\u662f\u8fd9\u6837\uff0c\u81f3\u4e8e\u4e00\u4e9b\u66f4\u7ec6\u8282\u7684\u8bc1\u660e\uff0c\u8fd9\u8fb9\u5efa\u8bae\u770b<a href=\"https:\/\/www.luogu.com.cn\/problem\/solution\/P4777\">\u6a21\u677f\u9898\u9898\u89e3\u533a<\/a>\uff0c\u5927\u4f6c\u4eec\u8bb2\u7684\u66f4\u597dorz\u3002<\/p>\n<h2>\u5b9e\u73b0<\/h2>\n<p>\u5b9e\u73b0\u8d77\u6765\u6709\u70b9\u4e0d\u592a\u597d\u5199\uff0c\u8fd9\u91cc\u7684\u5199\u6cd5\u501f\u9274\u4e86\u9898\u89e3\u533a\u7684\u5927\u4f6c\u7684\u5199\u6cd5\u3002<\/p>\n<pre><code class=\"language-c++\">ll mul(ll n, ll k, ll mod) {    \/\/\u9f9f\u901f\u4e58\n    ll ans = 0;\n    while (k) {\n        if (k &amp;amp; 1) ans = (ans + n) % mod;\n        k &amp;gt;&amp;gt;= 1;\n        n = (n + n) % mod;\n    }\n    return ans;\n}\n\nll exCRT() {\n    ll ans = c[1];\n    ll M = b[1];\n    for (int i = 2; i &amp;lt;= n; i++) {\n        ll x, y, C = ((c[i] - ans) % b[i] + b[i]) % b[i];\n        ll g = exgcd(M, b[i], x, y);\/\/\u6c42x*b[i-1]-y*b[i]=gcd(b[i-1],b[i])\u7684\u89e3\n        x = mul(x, C \/ g, b[i]);    \/\/\u9f9f\u901f\u4e58\uff0c\u6c42\u539f\u65b9\u7a0bx*b[i-1]-y*b[i]=c[i]-c[i-1]\u7684\u89e3\n        ans += M * x;\n        M *= b[i] \/ g;\n        ans = (ans + M) % M;    \/\/\u66f4\u65b0\u901a\u89e3\n    }\n    return ans;\n}<\/code><\/pre>\n<h1>\u603b\u7ed3<\/h1>\n<p>\u7559\u5751\uff0c\u7b49\u6211\u5199\u70b9\u9898\u518d\u6765\u5199orz\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5b9a\u4e49 \u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\uff08Chinese Remainder Theorem\uff0cCRT\uff09\uff0c\u53ef\u7528\u4e8e\u6c42\u89e3\u5982\u4e0b\u5f62\u5f0f\u7684\u4e00\u5143\u7ebf\u6027 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,3,6],"tags":[],"class_list":["post-375","post","type-post","status-publish","format-standard","hentry","category-c","category-oi","category-6"],"_links":{"self":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/375","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/comments?post=375"}],"version-history":[{"count":3,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/375\/revisions"}],"predecessor-version":[{"id":539,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/posts\/375\/revisions\/539"}],"wp:attachment":[{"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/media?parent=375"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/categories?post=375"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.xgnd.net\/index.php\/wp-json\/wp\/v2\/tags?post=375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}