{"id":620,"date":"2020-06-11T22:10:18","date_gmt":"2020-06-11T14:10:18","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=620"},"modified":"2021-05-14T22:08:53","modified_gmt":"2021-05-14T14:08:53","slug":"%e7%ae%80%e5%8d%95%e6%95%b0%e8%ae%ba%e7%9f%a5%e8%af%86%e7%82%b9","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/06\/11\/%e7%ae%80%e5%8d%95%e6%95%b0%e8%ae%ba%e7%9f%a5%e8%af%86%e7%82%b9\/","title":{"rendered":"\u7b80\u5355\u6570\u8bba\u77e5\u8bc6\u70b9"},"content":{"rendered":"

\u5e38\u7528\u7b26\u53f7\u7ea6\u5b9a<\/h4>\n

d|n<\/code>\u5f53n\u4e3a\u5e38\u6570\uff0c\u800cd\u4e3a\u53d8\u91cf\u65f6\uff0c\u8868\u793a\u679a\u4e3en\u7684\u6240\u6709\u7ea6\u6570\uff1b\u53cd\u4e4b\uff0c\u82e5d\u4e3a\u5e38\u6570n\u4e3a\u53d8\u91cf\uff0c\u5219\u8868\u793a\u679a\u4e3ed\u7684\u6240\u6709\u500d\u6570(d,2d,3d...)\u3002
\n[x]<\/code>\u6761\u4ef6\u51fd\u6570\uff0c\u5f53\u62ec\u53f7\u91cc\u7684\u8868\u8fbe\u5f0f\u4e3a\u771f\u65f6\uff0c\u51fd\u6570\u503c\u4e3a1\uff0c\u5426\u5219\u4e3a0
\na \\perp b<\/code>\u8868\u793aa\uff0cb\u4e92\u8d28<\/p>\n

\u6700\u5927\u516c\u7ea6\u6570<\/h4>\n

\u4e24\u4e2a\u6570\u7684\u6700\u5927\u516c\u7ea6\u6570(greatest common divisor)\u8868\u793a\u4e3agcd(a, b)<\/code>\u6216\u8005(a, b)<\/code>\uff0c\u5f53\u4e14\u4ec5\u5f53(a, b)=1<\/code>\u65f6\uff0ca\u548cb\u4e92\u8d28\u3002
\n\u6c42\u6700\u5927\u516c\u7ea6\u6570\u7684\u7b97\u6cd5\uff1agcd(a, b) = gcd(b, a%b)<\/code><\/p>\n

int gcd(int a, int b) {\n    return b==0? a:gcd(b, a%b);\n}<\/code><\/pre>\n
\u8fd8\u6709\u4e00\u79cd\u6c42\u6700\u5927\u516c\u7ea6\u6570\u7684\u7b97\u6cd5\uff1a\u66f4\u76f8\u51cf\u635f\u672f\u3002gcd(a, b) = gcd(a, a-b)<\/code>\u3002\u8fd9\u4e2a\u7b97\u6cd5\u4f7f\u5f97\u5927\u4e8e2\u7684\u6240\u6709\u7684\u6570\u7684\u6b27\u62c9\u51fd\u6570\u503c\u90fd\u662f\u5076\u6570\uff0c\u56e0\u4e3a\u548c\u4e00\u4e2a\u6570\u4e92\u8d28\u7684\u6570\u603b\u662f\u6210\u5bf9\u51fa\u73b0\u7684\u3002
\n\u540c\u65f6\u6839\u636e\u4ee5\u4e0a\u7b97\u6cd5\uff0c\u6211\u4eec\u8fd8\u80fd\u5f97\u51fa\u4e0en\u4e92\u8d28\u7684\u6570\u7684\u603b\u548c\u4e3an*\\frac{\u03a6(n)}{2}<\/code>\u3002\u56e0\u4e3a\u5171\u6709\\frac{\u03a6(n)}{2}<\/code>\u5bf9\u8d28\u6570\uff0c\u6bcf\u5bf9\u548c\u4e3an<\/code>\u3002
\n\u6b27\u62c9\u51fd\u6570\u8fd8\u6709\u4e00\u5927\u6027\u8d28\uff0c\u6b27\u62c9\u53cd\u6f14<\/strong>
\n\u6211\u4eec\u5b9a\u4e49\u4e00\u4e2a\u51fd\u6570f(n) = \\sum_{d|n} \u03a6(d)<\/code>\u3002\u5373n\u7684\u6240\u6709\u7ea6\u6570\u7684\u6b27\u62c9\u51fd\u6570\u4e4b\u548c\u3002\u8fd9\u4e2a\u51fd\u6570\u6ee1\u8db3\u4ee5\u4e0b\u6027\u8d28\uff1a<\/p>\n
\n
f(n)<\/code>\u662f\u79ef\u6027\u51fd\u6570\u3002f(mn)=f(m)f(n)<\/code>
\nf(p^k) = \u03a6(1) + \u03a6(p) + \u03a6(p^2) + \u00b7\u00b7\u00b7 + \u03a6(p^k) = 1 + (p-1) + (p^2-p) + \u00b7\u00b7\u00b7 + (p^k-p^{k-1}) = p^k<\/code>
\nf(n) = f(\\prod p_i^{q_i}) = \\prod f(p_i^{q_i}) = \\prod p_i^{q_i} = n<\/code>\u3002<\/p>\n<\/blockquote>\n
\u6b27\u62c9\u51fd\u6570<\/h4>\n
\u8bben\u662f\u81ea\u7136\u6570\uff0c\u6570\u52171,2,...,n\u4e2d\u4e0en\u4e92\u7d20\u7684\u6570\u7684\u4e2a\u6570\u79f0\u4e3an\u7684Euler\u51fd\u6570\uff0c\u8bb0\u4f5c\u03a6(n)\u3002
\n\u8ba1\u7b97\u516c\u5f0f\uff1a\u03a6(n) = n (1-\\frac{1}{p1}) (1-\\frac{1}{p2})\u00b7\u00b7\u00b7(1-\\frac{1}{p3})<\/code><\/p>\n
pi\u4e3an\u7684\u4e92\u4e0d\u4e0d\u76f8\u7b49\u7684\u7d20\u56e0\u5b50\u3002
\n\u6027\u8d28<\/p>\n
\n
\u82e5p\u662f\u7d20\u6570\uff0c\u5219\u03a6(p)= p-1\u3002
\n\u8bbep\u548cq\u662f\u7d20\u6570\uff0c\u5bf9n=pq\uff0c\u6709 \u03a6(n)= \u03a6(p) \u03a6(q)= (p-1)(q-1)<\/p>\n<\/blockquote>\n
\u6b27\u62c9\u5b9a\u7406<\/h4>\n
\u5bf9\u4efb\u610f\u6574\u6570a\u548cn\u4e92\u7d20\uff0c\u5219a^{\u03a6(n)}=1 (mod n)<\/code>
\n\u7279\u6b8a\u7684\uff0c\u5f53n\u4e3a\u7d20\u6570\u65f6\uff0c\u6709\u8d39\u9a6c\u5c0f\u5b9a\u7406\uff1aa^{n-1}=1 (mod n)<\/code>
\n\u6b27\u62c9\u5b9a\u7406\u9002\u7528\u4e8e\u5e42\u4e3a\u8d1f\u6570\u7684\u60c5\u51b5\u3002
\n\u82e5a\u548cn\u4e92\u7d20\uff0c\u5219\u6709a^{-1} \\equiv a^{\u03a6(n)-1}modn<\/code>\u3002
\n\u5f53n\u4e3a\u8d28\u6570\u65f6\uff0ca\u5173\u4e8en\u7684\u9006\u5143\u4e3aa^{-1} \\equiv a^{n-1-1}modn<\/code><\/p>\n
\u6269\u5c55\u6b27\u62c9\u5b9a\u7406<\/h4>\n
\u6269\u5c55\u6b27\u62c9\u5b9a\u7406\u662f\u7531\u6b27\u62c9\u5b9a\u7406\u63a8\u5f97\u7684\u3002\u6269\u5c55\u6b27\u62c9\u5b9a\u7406\u4e0d\u9002\u7528\u4e8e\u6c42\u5e42\u4e3a\u8d1f\u6570\u7684\u60c5\u51b5\u3002<\/p>\n
a, n\u4e92\u7d20\uff0c\u5373(a,n)=1\u65f6\uff0ca^b \u2261 a^{b\\%\u03a6(n)}modn<\/code>\u8fd9\u662f\u4e0d\u7528\u8d28\u7591\u7684\uff0c\u6b27\u62c9\u5b9a\u7406\u3002
\na, n\u4e0d\u4e92\u7d20\u65f6\uff0c\u82e5b<\u03a6(n)<\/code>\uff0c\u90a3\u4e48a^b \u2261 a^{b}modn<\/code>\uff0c\u8fd9\u65f6\u5019b\u7684\u503c\u5e94\u8be5\u4e0d\u4f1a\u592a\u5927\uff0c\u4e5f\u5bb9\u6613\u8ba1\u7b97\u3002
\na, n\u4e0d\u4e92\u7d20\u65f6\uff0c\u82e5b>=\u03a6(n)<\/code>\uff0c\u90a3\u4e48a^b \u2261 a^{b\\%\u03a6(n)+\u03a6(n)}modn<\/code>\uff0cb\u4e5f\u4e0d\u4f1a\u592a\u5927\uff0c\u4e5f\u597d\u8ba1\u7b97\u3002<\/p>\n
\u540c\u4f59\u65b9\u7a0b<\/h4>\n
\u6c42\u65b9\u7a0bax \\equiv 1(modb)<\/code>\u7684\u6700\u5c0f\u6b63\u6574\u6570\u89e3\u3002
\n\u628a\u65b9\u7a0b\u8868\u793a\u6210ax + by = 1<\/code>\u7684\u5f62\u5f0f\uff0c\u6839\u636e\u88f4\u5c5e\u5b9a\u7406\uff0c\u82e5(a,b)!=1<\/code>\uff0c\u5219\u65b9\u7a0b\u65e0\u89e3\u3002\u5229\u7528\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u6c42\u5f97\u4e00\u7ec4\u89e3\u540e\uff0c\u5176\u4f59\u89e3\u53ef\u7531\u8be5\u89e3\u63a8\u51fa\uff1ax = x_0 + bt, y = y_0 + at<\/code>\u3002<\/p>\n
\u540c\u4f59\u65b9\u7a0b<\/a><\/p>\n
#include <bits\/stdc++.h>\n\nusing namespace std;\ntypedef long long ll;\nvoid extgcd(ll a, ll b, ll &x, ll &y) {\n    if (b == 0) {\n        x = 1, y = 0;\n        return;\n    }\n\n    extgcd(b, a % b, y, x);\n    y -= a \/ b * x;\n    return;\n}\n\nint main() {\n    ll a, b, x, y;\n    cin >> a >> b;\n    extgcd(a, b, x, y);\n    cout << (x % b + b) % b << endl;\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u5e38\u7528\u7b26\u53f7\u7ea6\u5b9a d|n\u5f53n\u4e3a\u5e38\u6570\uff0c\u800cd\u4e3a\u53d8\u91cf\u65f6\uff0c\u8868\u793a\u679a\u4e3en\u7684\u6240\u6709\u7ea6\u6570\uff1b\u53cd\u4e4b\uff0c\u82e5d\u4e3a\u5e38\u6570n\u4e3a\u53d8\u91cf\uff0c\u5219\u8868\u793a […]<\/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\/620"}],"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=620"}],"version-history":[{"count":27,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/620\/revisions"}],"predecessor-version":[{"id":1223,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/620\/revisions\/1223"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=620"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=620"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=620"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}