{"id":1240,"date":"2021-05-23T18:42:37","date_gmt":"2021-05-23T10:42:37","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=1240"},"modified":"2021-05-23T21:02:14","modified_gmt":"2021-05-23T13:02:14","slug":"%e5%8e%9f%e6%a0%b9","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2021\/05\/23\/%e5%8e%9f%e6%a0%b9\/","title":{"rendered":"\u539f\u6839"},"content":{"rendered":"

\u9636<\/h4>\n

\u7531\u6b27\u62c9\u5b9a\u7406\u53ef\u77e5\uff0c\u5bf9\u4e8ea \\in \\mathbb{Z}, m \\in \\mathbb{N^{*}}<\/code>\uff0c\u82e5gcd(a, m)=1<\/code>\uff0c\u5219a^{ \\phi(m) } \\equiv 1(mod m)<\/code>\u3002\u56e0\u6b64\u6ee1\u8db3a^n \\equiv 1(modm)<\/code>\u7684\u6700\u5c0f\u6b63\u6574\u6570n\u5b58\u5728\uff0c\u8fd9\u4e2a\u6700\u5c0f\u7684n\u5c31\u79f0\u4f5ca\u6a21m\u7684\u9636\uff0c\u8bb0\u4f5c\\delta_{m}(a)<\/code>\u3002
\n\u6ce8\u610f\u9636\u4e0d\u4e00\u5b9a\u5c31\u7b49\u4e8e\\phi(m)<\/code>\uff0c\u4e5f\u53ef\u80fd\u662f\u5b83\u7684\u7ea6\u6570\u3002
\n\u5927\u8111\u91cc\u6784\u60f3\u8fd9\u73a9\u610f\u7684\u65f6\u5019\uff0c\u4e00\u5b9a\u8981\u548cm\u7684\u6b27\u62c9\u51fd\u6570\\phi(m)<\/code>\u53ca\u5176\u7ea6\u6570\u8054\u7cfb\u8d77\u6765\u3002<\/p>\n

\u6027\u8d28<\/strong>
\n1.a,a^1,a^2\u00b7\u00b7\u00b7a^{ \\delta_m (a) }<\/code>\u6a21m\u4e24\u4e24\u4e0d\u540c\u3002\u8fd9\u5f88\u597d\u60f3\uff0c\u6bcf\u4e00\u9636\u5c31\u662f\u4e00\u4e2a\u5faa\u73af\u3002
\n2.\u82e5a^{ n } \\equiv 1(modm)<\/code>\uff0c\u5219\\delta_{m}(a) | n<\/code>\u3002
\n3.\u5bf9a,b \\in \\mathbb{Z}, m \\in \\mathbb{N^{*}}<\/code>\uff0c\u82e5gcd(a,m)=gcd(b,m)=1<\/code>\uff0c\u5219\\delta(ab)=\\delta(a)\\delta(b) \\Leftrightarrow gcd(\\delta(a),\\delta(b))=1<\/code>\u3002
\n4.\u8bbek \\in \\mathbb{N}, m \\in \\mathbb{N^*},a \\in \\mathbb{Z}, gcd(a,m)=1<\/code>\uff0c\u5219\\delta_m(a^k)= \\frac{ \\delta_m(a) }{ gcd(\\delta_m(a), k) }<\/code>\u3002\u5229\u7528\u8fd9\u4e00\u6027\u8d28\u5feb\u901f\u6c42\u6240\u6709\u539f\u6839\u3002<\/p>\n

\u539f\u6839<\/h4>\n

\u8bbea \\in \\mathbb{Z}, m \\in \\mathbb{N^{*}}<\/code>\uff0c\u82e5gcd(a, m)=1<\/code>\u4e14\\delta_{m}(a)=\\phi(m)<\/code>\uff0c\u5219a\u662fm\u7684\u4e00\u4e2a\u539f\u6839\u3002<\/p>\n

\u6839\u636e\u4e0a\u9762\u9636\u7684\u5b9a\u4e49\uff0c\u90a3\u4e48\u5224\u65ada\u662f\u5426\u4e3am\u7684\u4e00\u4e2a\u539f\u6839\uff0c\u53ea\u8981\u5224\u65ad\u548c\\phi(m)<\/code>\u7684\u6240\u6709(\u9664\u53bb1\u548c\u5b83\u81ea\u8eab)\u7684\u7ea6\u6570x\u662f\u5426\u6ee1\u8db3a^x \\equiv 1(modm)<\/code>\u5373\u53ef\uff0c\u82e5\u90fd\u4e0d\u6ee1\u8db3\uff0c\u5219a\u662fm\u7684\u4e00\u4e2a\u539f\u6839\u3002<\/p>\n

\u4e00\u4e2a\u6570m\u5b58\u5728\u539f\u6839\u5f53\u4e14\u4ec5\u5f53m=2,4,p^{\\alpha}, 2p^{\\alpha},p\u4e3a\u5927\u4e8e2\u7684\u8d28\u6570, \\alpha \\in \\mathbb{N^*}<\/code>\u3002\u4e14m\u7684\u539f\u6839\u4e2a\u6570\u4e3a\\phi( \\phi(m) )<\/code>\u3002
\n\u82e5m\u5b58\u5728\u539f\u6839\uff0c\u5219\u5176\u6700\u5c0f\u539f\u6839\u662f\u4e0d\u591a\u4e8em^{0.25}<\/code>\u7ea7\u522b\u7684\u3002\u53ef\u4ee5\u66b4\u529b\u5bfb\u627em\u7684\u7b2c\u4e00\u4e2a\u539f\u6839\u3002<\/p>\n

\u5feb\u901f\u6c42\u6240\u6709\u539f\u6839<\/h4>\n

\u6761\u4ef6\u4ecd\u4e3a\u4e0a\u8ff0\u6761\u4ef6\uff0c\u9996\u5148\u9700\u8981\u7279\u52242\u548c4\uff0c\u4ee5\u53cam\u662f\u5426\u6709\u539f\u6839\u3002\u786e\u5b9am\u6709\u539f\u6839\u4e4b\u540e\uff0c\u7136\u540e\u6c42\u51fam\u6700\u5c0f\u7684\u539f\u6839a\u3002\u679a\u4e3e\\phi(m)<\/code>\u7684\u6240\u6709(\u4e0d\u4e3a1\u548c\u5b83\u672c\u8eab)\u7ea6\u6570x\uff0c\u82e5\u90fd\u4e0d\u6ee1\u8db3a^x \\equiv 1(modm)<\/code>\uff0c\u5219a\u5c31\u662f\u6700\u5c0f\u7684\u539f\u6839\u3002
\n\u7136\u540e\u518d\u679a\u4e3e[1,\\phi(m)]<\/code>\u4e2d\u548c\\phi(i)<\/code>\u4e92\u8d28\u7684\u90a3\u4e9b\u6570k(\u5305\u62ec1)\uff0c\u6bcf\u4e00\u4e2aa^k<\/code>\u90fd\u662f\u4e00\u4e2a\u539f\u6839\u3002\u90a3\u4e48\u603b\u5171\u6709\\phi( \\phi(m) )<\/code>\u4e2a\u539f\u6839\u3002<\/p>\n

\u5bf9\u4e8e\u4e0a\u8ff0\u6b65\u9aa4\u7684\u7b2c\u4e8c\u90e8\u5206\uff0c\u8bc1\u660e\u4e3a\uff1a\u5229\u7528\u4e0a\u8ff0\u9636\u90e8\u5206\u7684\u6027\u8d284\uff0c\u82e5\u5df2\u6c42\u5f97\u6700\u5c0f\u539f\u6839a\uff0ck\u6ee1\u8db3gcd( \\phi(m),k )=1<\/code>\uff0c\u5219\u6709\\delta_m (a^k) = \\delta_m(a) = \\phi(m)<\/code>\uff0c\u90a3\u4e48a^k<\/code>\u4e5f\u662fm\u7684\u4e00\u4e2a\u539f\u6839\u3002<\/p>\n

P6091 \u3010\u6a21\u677f\u3011\u539f\u6839
\n<\/a>
\nT\u7ec4\u6570\u636e\uff0c\u6bcf\u6b21\u8f93\u5165n\uff0cd\uff0c\u6c42n\u7684\u6240\u6709\u539f\u6839\uff0c\u8f93\u51fa\u539f\u6839\u4e2a\u6570\uff0c\u6bcfd\u4e2a\u8f93\u51fa\u4e00\u4e2a\u3002<\/p>\n

#include <cstdio>\n#include <queue>\n#include <algorithm>\nusing namespace std;\ntypedef long long ll;\n\nconst int maxn = 1e2+5;\n\nint m, d;\nint prime[maxn], cnt, phi[maxn];\nbool vis[maxn];\n\nint q[maxn], cnt2;\nint A[maxn];\n\nvoid init() {\n    int n = maxn-5;\n    phi[1] = 1;\n    for (int i=2; i<=n; i++) {\n        if (!vis[i])    prime[++cnt] = i, phi[i] = i-1;\n        for (int j=1; j<=cnt && i*prime[j]<=n; j++) {\n            vis[i*prime[j]] = 1;\n            if (i%prime[j]==0) {\n                phi[i*prime[j]] = phi[i] * prime[j];\n                break;\n            }\n            phi[i*prime[j]] = phi[i] * phi[prime[j]];\n        }\n    }\n    \/\/for (int i=1; i<=n; i++)    vis[i] = 0;\n    return;\n}\n\ninline ll pow_mod(ll a, ll b, const ll &mod) {\n    if (0==a)   return 0;\n    ll ans = 1;\n    while ( b )\n    {\n        if (b&1)    ans = ans*a%mod;\n        b >>= 1;\n        a = a*a%mod;\n    }\n    return ans;\n}\n\nint gcd(int a, int b) {\n    return b==0? a:gcd(b, a%b);\n}\n\nint main() {\n    int t;\n    scanf ("%d", &t);\n    init();\n    while (t--) {\n        scanf ("%d %d", &m, &d);\n        if (m!=2 && m!=4) {\n            int tmp = m;\n            if (tmp%2==0) tmp \/= 2;\n            if (tmp==1 || tmp%2==0) {\n                puts("0\\n");\n                continue;\n            }\n            for (int i=2; i<=cnt; i++) if (tmp%prime[i]==0){\n                while (tmp%prime[i]==0) tmp \/= prime[i];\n                break;\n            }\n            if (tmp!=1) {\n                puts("0\\n");\n                continue;\n            }\n        }\n        int tmp = phi[m], a;\n        cnt2 = 0;\n        for (int i=1; i<=tmp; i++) if (tmp%i==0){\n            q[++cnt2] = i;\n        }\n        for (int i=2; i<tmp; i++) if (gcd(i,m)==1){\n            bool flag = true;\n            for (int j=2; j<cnt2; j++) if ( pow_mod(i, q[j], m)==1 ){\n                flag = false;\n                break;\n            }\n            if (flag) {\n                a = i;\n                break;\n            }\n        }\n        int ans = 0;\n        printf ("%d\\n", phi[tmp]);\n        if (m==2 || m==4) {\n            A[++ans] = m-1;\n        }else {\n            A[++ans] = a;\n            for (int i=2; i<tmp; i++) if ( gcd(i,tmp)==1 ) {\n                A[++ans] = pow_mod(a, i, m);\n            }\n        }\n        sort (A+1, A+ans+1);\n        for (int i=d; i<=ans; i+=d) {\n            printf ("%d", A[i]);\n            if (i+d<=ans) putchar(' ');\n        }\n        if (t)  putchar('\\n');\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9636 \u7531\u6b27\u62c9\u5b9a\u7406\u53ef\u77e5\uff0c\u5bf9\u4e8ea \\in \\mathbb{Z}, m \\in \\mathbb{N^{*}} […]<\/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\/1240"}],"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=1240"}],"version-history":[{"count":13,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/1240\/revisions"}],"predecessor-version":[{"id":1253,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/1240\/revisions\/1253"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=1240"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=1240"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=1240"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}