{"id":1199,"date":"2021-05-13T21:11:10","date_gmt":"2021-05-13T13:11:10","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=1199"},"modified":"2021-05-14T16:50:40","modified_gmt":"2021-05-14T08:50:40","slug":"%e4%b8%ad%e5%9b%bd%e5%89%a9%e4%bd%99%e5%ae%9a%e7%90%86","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2021\/05\/13\/%e4%b8%ad%e5%9b%bd%e5%89%a9%e4%bd%99%e5%ae%9a%e7%90%86\/","title":{"rendered":"\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406"},"content":{"rendered":"<h4>\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406<\/h4>\n<p>\u8bbe\u4e00\u4e2a\u6570x\uff0c\u518d\u7ed9\u5b9ak\u7ec4\u6570a\uff0cn\uff0c\u6ee1\u8db3k\u4e2a\u65b9\u7a0b<code class=\"katex-inline\">x \\equiv a_{i}(mod n_{i})<\/code>\uff0c\u4e14a\u4e4b\u95f4\u4e24\u4e24\u4e92\u8d28\uff0c\u6c42x\u7684\u6700\u5c0f\u53ef\u80fd\u503c\uff0cx\u662f\u6b63\u6574\u6570\u3002<\/p>\n<p>\u5728\u95ee\u9898\u4e2d\uff0cn\u662f\u6a21\u6570\uff0ca\u662f\u4f59\u6570\uff0c\u7b97\u6cd5\u6d41\u7a0b\uff1a<br \/>\n1.\u8ba1\u7b97\u6240\u6709\u6a21\u6570\u7684\u79efn<br \/>\n2.\u5bf9\u4e8e\u7b2ci\u7ec4\u65b9\u7a0b\uff1a\u8ba1\u7b97 <code class=\"katex-inline\">m_i = \\frac{n}{n_i}<\/code>\u548c<code class=\"katex-inline\">m_i<\/code>\u5728\u6a21<code class=\"katex-inline\">n_i<\/code>\u610f\u4e49\u4e0b\u7684\u9006\u5143<code class=\"katex-inline\">m_i^{-1}<\/code>\uff0c\u4ee4<code class=\"katex-inline\">c_i = m_im_i^{-1}<\/code>\uff0c\u4e0d\u53d6\u6a21\u3002<br \/>\n3.<code class=\"katex-inline\">x = \\sum a_ic_i(modn)<\/code><\/p>\n<h5><a href=\"https:\/\/www.acwing.com\/problem\/content\/description\/1300\/\">\u66f9\u51b2\u79f0\u8c61<\/a><\/h5>\n<pre><code class=\"language-c++\">#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\ntypedef long long ll;\nint A[11], B[11];\n\nvoid extgcd(ll a, ll b, ll &amp;x, ll &amp;y) {\n    if (b==0) {\n        x = 1, y = 0;\n        return;\n    }\n    extgcd(b, a%b, y, x);\n    y -= a\/b*x;\n    return;\n}\n\nint main() {\n    int n;\n    ll ans = 0;\n    cin &gt;&gt; n;\n    ll tmp = 1;\n    for (int i=1; i&lt;=n; i++) {\n        cin &gt;&gt; A[i] &gt;&gt; B[i];\n        tmp *= A[i];\n    }\n    for (int i=1; i&lt;=n; i++) {\n        ll x, y;\n        extgcd(tmp\/A[i], A[i], x, y);\n        ans += (ll)B[i] * (tmp\/A[i]) * x;\n    }\n    cout &lt;&lt; (ans%tmp + tmp) % tmp;\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406 \u8bbe\u4e00\u4e2a\u6570x\uff0c\u518d\u7ed9\u5b9ak\u7ec4\u6570a\uff0cn\uff0c\u6ee1\u8db3k\u4e2a\u65b9\u7a0bx \\equiv a_{i}(mod n_ [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[60],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/1199"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=1199"}],"version-history":[{"count":3,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/1199\/revisions"}],"predecessor-version":[{"id":1215,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/1199\/revisions\/1215"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=1199"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=1199"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=1199"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}