{"id":1216,"date":"2021-05-14T16:53:47","date_gmt":"2021-05-14T08:53:47","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=1216"},"modified":"2021-05-15T11:00:32","modified_gmt":"2021-05-15T03:00:32","slug":"%e4%b9%98%e6%b3%95%e9%80%86%e5%85%83","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2021\/05\/14\/%e4%b9%98%e6%b3%95%e9%80%86%e5%85%83\/","title":{"rendered":"\u4e58\u6cd5\u9006\u5143"},"content":{"rendered":"<h3>\u4e58\u6cd5\u9006\u5143<\/h3>\n<p>\u5982\u679c\u4e00\u4e2a\u7ebf\u6027\u65b9\u7a0b<code class=\"katex-inline\">ax \\equiv 1(mod b)<\/code>\uff0c\u5219x\u79f0\u4e3a<code class=\"katex-inline\">a(mod)b<\/code>\u7684\u9006\u5143\uff0c\u5373<code class=\"katex-inline\">x = a^{-1}<\/code>\u3002<\/p>\n<p>\u4e0b\u9762\u4ecb\u7ecd\u6c42\u9006\u5143\u7684\u51e0\u79cd\u65b9\u6cd5\u3002<\/p>\n<h5>(\u5355\u4e2a)\u6269\u5c55\u6b27\u51e0\u91cc\u5f97<\/h5>\n<p>\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u662f\u7528\u6765\u6c42\u65b9\u7a0b<code class=\"katex-inline\">ax + by = gcd(a, b)<\/code>\u7684\u89e3\u7684\u3002<br \/>\n\u5f53ab\u4e0d\u4e92\u8d28\u65f6\uff0ca\u5173\u4e8e\u4ee4\u4e00\u4e2a\u6570b\u7684\u9006\u5143\u662f\u4e0d\u4e00\u5b9a\u5b58\u5728\u7684\uff0c\u6211\u4eec\u5148\u628a\u4e0a\u8ff0\u7ebf\u6027\u65b9\u7a0b\u8fdb\u884c\u8f6c\u5316\uff1a<code class=\"katex-inline\">ax + by = 1<\/code>\uff0c\u6839\u636e\u88f4\u5c5e\u5b9a\u7406\uff1a<code class=\"katex-inline\">ax + by = gcd(a, b)<\/code>\u6709\u89e3\uff0c\u82e5<code class=\"katex-inline\">gcd(a, b)!=1<\/code>\uff0c\u5219\u89e3\u4e0d\u4e00\u5b9a\u5b58\u5728\u3002<\/p>\n<pre><code class=\"language-c++\">void extgcd(int a, int 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}<\/code><\/pre>\n<h5>(\u5355\u4e2a)\u8d39\u9a6c\u5c0f\u5b9a\u7406<\/h5>\n<p>\u5f53p\u4e3a\u8d28\u6570\u65f6\uff0c<code class=\"katex-inline\">a^{p-1} \\equiv 1(modp)<\/code>\u3002<br \/>\n<code class=\"katex-inline\">a^{-1} = a^{p-2}(modp)<\/code>\uff0c\u5feb\u901f\u5e42\u6c42\u89e3\u3002<\/p>\n<h4>(\u591a\u4e2a)\u6b27\u62c9\u7b5b<\/h4>\n<p>\u56e0\u4e3a\u9006\u5143\u662f\u5b8c\u5168\u79ef\u6027\u51fd\u6570\uff0c\u6240\u4ee5\u53ef\u4ee5\u7ebf\u7b5b\u5f97\u5230\u3002<br \/>\n<code class=\"katex-inline\">a*inv(a)=1(modp), b*inv(b)=1(modp),a*inv(a)*b*inv(b)=(a*b)*(inv(a)*inv(b))=1(modp)<\/code><\/p>\n<h5>(\u591a\u4e2a)\u7ebf\u6027\u6c42<\/h5>\n<p>\u5b9e\u5728\u592a\u61d2\u4e86\uff0c\u8d34\u4e2a\u522b\u4eba\u7684\u8bc1\u660e\u5427...<br \/>\n<img src=\"http:\/\/www.zyhcoding.club:80\/wp-content\/uploads\/2021\/05\/\u7ebf\u6027\u6c42\u9006\u5143.png\" alt=\"\u7ebf\u6027\u6c42\u9006\u5143\" \/><\/p>\n<pre><code class=\"language-c++\">inv[1] = 1;\nfor(int i=2; i&lt;=n; i++)\n    inv[i] = (p - p \/ i) * inv[p % i] % p;<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4e58\u6cd5\u9006\u5143 \u5982\u679c\u4e00\u4e2a\u7ebf\u6027\u65b9\u7a0bax \\equiv 1(mod b)\uff0c\u5219x\u79f0\u4e3aa(mod)b\u7684\u9006\u5143\uff0c\u5373x  [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[48],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/1216"}],"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=1216"}],"version-history":[{"count":6,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/1216\/revisions"}],"predecessor-version":[{"id":1221,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/1216\/revisions\/1221"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=1216"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=1216"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=1216"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}