{"id":374,"date":"2022-09-20T16:06:03","date_gmt":"2022-09-20T08:06:03","guid":{"rendered":"https:\/\/blog.cirno.fun\/?p=374"},"modified":"2024-09-12T09:33:52","modified_gmt":"2024-09-12T01:33:52","slug":"%e6%ac%a7%e6%8b%89%e5%87%bd%e6%95%b01","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=374","title":{"rendered":"\u6b27\u62c9\u51fd\u6570\u521d\u6b65"},"content":{"rendered":"<p>\u6765\u770b\u4e00\u4e0b\u6b27\u62c9\u51fd\u6570\u7684\u5b9a\u4e49\uff1a<\/p>\n<blockquote>\n<p>\u5728\u6570\u8bba\uff0c\u5bf9\u6b63\u6574\u6570n\uff0c\u6b27\u62c9\u51fd\u6570\u662f\u5c0f\u4e8en\u7684\u6b63\u6574\u6570\u4e2d\u4e0en\u4e92\u8d28\u7684\u6570\u7684\u6570\u76ee.<\/p>\n<\/blockquote>\n<p>\u6b27\u62c9\u51fd\u6570\u8bb0\u4e3a<\/p>\n<pre><code class=\"language-katex\">\\phi (x)<\/code><\/pre>\n<p>\u4f8b\uff1a<\/p>\n<pre><code class=\"language-katex\">\\phi (6)=2\uff0c\n\u56e0\u4e3a\\underline{1}  2 3 4 \\underline{5} 6<\/code><\/pre>\n<p>\u8bb0\u6570N\u5206\u89e3\u8d28\u56e0\u6570\u7684\u7ed3\u679c\u662f<\/p>\n<pre><code class=\"language-katex\">N=p_{1} ^{\\alpha1 }\\times p_{2} ^{\\alpha2}\\times p_{3} ^{\\alpha3}\\times\\cdot \\cdot \\cdot \\times p_{k} ^{\\alpha k}\n =\\prod_{i=1}^{k} p_{i} ^{\\alpha i}<\/code><\/pre>\n<p>\u5219<\/p>\n<pre><code class=\"language-katex\">\\phi (x)=N(1-\\frac{1}{p_{1}})(1-\\frac{1}{p_{2}})\\cdot \\cdot \\cdot (1-\\frac{1}{p_{k}})=N\\prod_{i=1}^{k}(1-p_{i})<\/code><\/pre>\n<p>\u4f8b\uff1a<\/p>\n<pre><code class=\"language-katex\">6=2^1\\times 3^1 \\\\\n\\phi (6)=6 \\times (1-\\frac{1}{2} )\\times (1-\\frac{1}{3} )=2<\/code><\/pre>\n<p>\u7b80\u8981\u8bc1\u660e\uff1a\uff08\u5bb9\u65a5\u539f\u7406\uff09 \u8981\u6c421\\~N\u4e2d\u4e92\u8d28\u7684\u6570\u7684\u4e2a\u6570\uff0c\u9996\u5148\u4ece1\\~N\u4e2d\u53bb\u6389Pi\u7684\u500d\u6570<\/p>\n<pre><code class=\"language-katex\">N-[\\frac{N}{p_{i}} ]<\/code><\/pre>\n<p>\u518d\u52a0\u4e0a\u6240\u6709Pi\u00b7Pj\u7684\u500d\u6570<\/p>\n<p>\u518d\u51cf\u53bb\u6240\u6709Pi\u00b7Pj\u00b7Pk\u7684\u500d\u6570<\/p>\n<p>\u00b7\u00b7\u00b7\u4ee5\u6b64\u7c7b\u63a8<\/p>\n<pre><code class=\"language-katex\">\\phi(N)=N-[\\frac{N}{P_i} ]+[\\frac{N}{p_ip_j} ]-[\\frac{N}{p_ip_jp_k} ]+\\cdot \\cdot \\cdot \\\\  =   N(1-\\frac{1}{p_{1}})(1-\\frac{1}{p_{2}})\\cdot \\cdot \\cdot (1-\\frac{1}{p_{k}})   =  N\\prod_{i=1}^{k}(1-p_{i})<\/code><\/pre>\n<p>\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0c\u5728\u7a0b\u5e8f\u4e2d\u56e0\u4e3aint\u7cbe\u5ea6\u95ee\u9898\uff0c\u4e00\u822c\u5c061-1\/Pi\u5199\u6210*(Pi-1)\/Pi<\/p>\n<pre><code class=\"language-cpp\">ll phi(int x){\/\/\u8fd4\u56dex\u7684phi(x)\u7684\u503c\n    ll res=x;\n    for(int i=2;i&lt;=x\/i;i++)\n        if(x%i==0){\n            res=res*(i-1)\/i;\/\/\u9700\u8981\u6ce8\u610f\u7cbe\u5ea6\u95ee\u9898\n            while(x%i==0)   x\/=i;\n        }\n    if(x&gt;1) res=res*(x-1)\/x;\/\/\u5982\u679c\u6b64\u65f6x&gt;1\uff0c\u5219x\u672c\u8eab\u662f\u4e00\u4e2a\u8f83\u5927\u7684\u8d28\u6570\n    return res;\n}<\/code><\/pre>\n<p>\u4e0d\u96be\u770b\u51fa\u6c42\u89e3\u6b27\u62c9\u51fd\u6570\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u548c\u5206\u89e3\u8d28\u56e0\u6570\u4e00\u6837\uff0c\u90fd\u662f<\/p>\n<pre><code class=\"language-katex\">O(\\sqrt N)<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u6765\u770b\u4e00\u4e0b\u6b27\u62c9\u51fd\u6570\u7684\u5b9a\u4e49\uff1a \u5728\u6570\u8bba\uff0c\u5bf9\u6b63\u6574\u6570n\uff0c\u6b27\u62c9\u51fd\u6570\u662f\u5c0f\u4e8en\u7684\u6b63\u6574\u6570\u4e2d\u4e0en\u4e92\u8d28 [&#8230;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13,16],"tags":[],"class_list":["post-374","post","type-post","status-publish","format-standard","hentry","category-13","category-16"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/374","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=374"}],"version-history":[{"count":1,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/374\/revisions"}],"predecessor-version":[{"id":749,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/374\/revisions\/749"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=374"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}