{"id":32,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-08-12-%e6%ac%a7%e6%8b%89%e5%87%bd%e6%95%b0\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-08-12-%e6%ac%a7%e6%8b%89%e5%87%bd%e6%95%b0","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-08-12-%e6%ac%a7%e6%8b%89%e5%87%bd%e6%95%b0\/","title":{"rendered":"2020-08-12  \u6b27\u62c9\u51fd\u6570"},"content":{"rendered":"<p><svg  style=\"display: none;\">\n                        <path stroke-linecap=\"round\" d=\"M5,0 0,2.5 5,5z\" id=\"raphael-marker-block\" style=\"-webkit-tap-highlight-color: rgba(0, 0, 0, 0);\"><\/path>\n                    <\/svg><\/p>\n<p><a href=\"http:\/\/icpc.upc.edu.cn\/problem.php?cid=2539&#038;pid=3\">http:\/\/icpc.upc.edu.cn\/problem.php?cid=2539&#038;pid=3<\/a><\/p>\n<h5><a id=\"_1\"><\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n<p>Q:KZB \u4f60\u6821\u672c SA \u505a\u5b8c\u505a\u4ec0\u4e48\u554a\uff1f<br \/> KZB: \u4f5c\u5f0a\uff08\u505a B\uff09\u554a<\/p>\n<p>\u6709\u4e00\u6b21\uff0c\u67d0\u7ea7\u67d0\u67d0\u73ed\u7684\u73ed\u4e3b\u4efb\u53bb\u67e5\u4e86\u76d1\u63a7\uff0c\u53d1\u73b0 KZB \u6709\u4eba\u6284\u4f5c\u4e1a\uff0c\u5c31\u628a\u5168\u73ed\u9a82\u4e86\u4e00\u901a\u3002<\/p>\n<p>\u4e3a\u4e86\u9632\u6b62\u8fd9\u7c7b\u4e8b\u60c5\u518d\u6b21\u53d1\u751f Jay \u5c31\u60f3\u51fa\u4e86\u4e00\u9053\u9898\u3002<\/p>\n<p>\u5047\u5982\u6574\u4e2a\u73ed\u4e3a\u4e00\u4e2an\u00d7n\u7684\u77e9\u9635\uff0c\u800c\u5728\u76d1\u63a7\u8f83\u524d\u9762\u7684\u4eba\u4f1a\u906e\u4f4f\u540e\u9762\u7684\u4eba\uff08\u8be6\u89c1\u540e\u9762\u7684\u6837\u4f8b\u89e3\u91ca\uff09\u3002\u6c42\u76d1\u63a7\u4e0d\u4f1a\u53d1\u73b0\u7684\u4eba\u6570\uff08\u5047\u8bbe\u76d1\u63a7\u9ad8\u5ea6\u4e3a1\uff09\u3002<\/p>\n<p>Tip: \u56e0\u4e3a\u76d1\u63a7\u5728(1,1)\u7684\u4f4d\u7f6e\uff0c\u6240\u4ee5\u4f1a\u5360\u4e00\u4e2a\u4f4d\u7f6e\u3002<\/p>\n<h5><a id=\"_12\"><\/a>\u8f93\u5165<\/h5>\n<p>\u4e00\u4e2a\u6570n\u3002<\/p>\n<h5><a id=\"_14\"><\/a>\u8f93\u51fa<\/h5>\n<p>\u4e00\u4e2a\u6570\uff0c\u5373\u76d1\u63a7\u4e0d\u4f1a\u770b\u5230\u7684\u5b66\u751f\u4eba\u6570\u3002<\/p>\n<h5><a id=\"_16\"><\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n<pre><code>6\n<\/code><\/pre>\n<h5><a id=\"_20\"><\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n<pre><code>14\n<\/code><\/pre>\n<h5><a id=\"_24\"><\/a>\u63d0\u793a<\/h5>\n<p>\u6837\u4f8b\u89e3\u91ca:\u5f53n=6\u65f6\uff0c\u5750\u5728(3,5)\u4e0a\u7684\u540c\u5b66\u4f1a\u88ab\u5750\u5728(2,3)\u4e0a\u7684\u540c\u5b66\u6321\u4f4f\uff0c\u4ee5\u6b64\u7c7b\u63a8\u3002<br \/> <img decoding=\"async\" src=\"https:\/\/imgconvert.csdnimg.cn\/aHR0cDovL2ljcGMudXBjLmVkdS5jbi91cGxvYWQvaW1hZ2UvMjAyMDA1MjkvMjAyMDA1MjkwODI2MjdfNDMxMzEuanBn?x-oss-process=image\/format,png#pic_center\" alt=\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"><\/p>\n<p>\u53ef\u4ee5\u53d1\u73b0\u5f53gcd(x,y)\u4e0d\u4e3a1\u65f6\u5373\u7167\u4e0d\u5230\uff0c\u6b27\u62c9\u51fd\u6570\u6c42n\u6570\u5b57\u4ee5\u5185\u7684\u8d28\u56e0\u6570\u5bf9\u6709\u591a\u5c11\u5373\u53ef\u3002<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/img-blog.csdnimg.cn\/20200812192004185.jpg?x-oss-process=image\/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjA0ODg0OA==,size_16,color_FFFFFF,t_70#pic_center\" alt=\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"><br \/> \u56fe\u4e3an\u4e3a5\u65f6\u7684\u89e3\u91ca\uff0c\u6807\u6ce8\u4e3a1\u7684\u662f\u76d1\u63a7\u80fd\u591f\u53d1\u73b0\u7684<br \/> \u6b27\u62c9\u51fd\u6570\u7b80\u4ecb\uff1a<br \/> <a href=\"https:\/\/zhuanlan.zhihu.com\/p\/42748145\">https:\/\/zhuanlan.zhihu.com\/p\/42748145<\/a><\/p>\n<pre><code>#include <iostream>\n#include <cstdio>\n#include <cstring>\n#include <cmath>\nusing namespace std;\ntypedef long long ll;\nll n, ans, pr[200507], ph[200507], cnt ;\nbool vis[200507] ;\n\nint main()  \/\/\u7ed3\u5408\u4e86\u6b27\u62c9\u7b5b\u6cd5\n{\n    ph[1] = 1 ;\n    scanf(\"%lld\", &n );\n    if(n==1||n==2)\n    {\n        cout<<0<<endl;\n        return 0;\n    }\n    for(ll  i = 2 ; i<=n-1; ++ i )  \/\/\u5206\u89e3\u8d28\u56e0\u6570\u548c\u521d\u59cb\u5316\n    {\n        if(!vis[i])\n        {\n            cnt ++ ;\n            pr[cnt] = i ;\n            ph[i] = i - 1 ;\n        }\n        for(ll j = 1 ; j <=cnt&#038;&#038;i*pr[j]<=n-1;++ j )  \/\/\u6b27\u62c9\u7b5b\u6cd5\n        {\n            vis[ i * pr[j] ] = 1 ;\n            if( i % pr[j] == 0 )\n            {\n                ph[ pr[j] * i ] = ph[i] * pr[j] ;\n                break;\n            }\n            else\n                ph [ pr[j] * i] = ph[i] * (pr[j] - 1 );\n        }\n    }\n    for(ll i = 2 ; i <= n-1 ; ++ i )\n        ans += ph[i];\/\/\u7d2f\u52a0\u7ed3\u679c\n    ans=ans*2+4;\n    ans=n*n-ans;\n    cout<<ans<<endl;\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>http:\/\/icpc.upc.edu.cn\/pr&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-32","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/32","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=32"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/32\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=32"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=32"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=32"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}