{"id":1046,"date":"2014-10-22T22:48:45","date_gmt":"2014-10-22T14:48:45","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1046"},"modified":"2014-10-22T22:48:45","modified_gmt":"2014-10-22T14:48:45","slug":"2014-acmicpc-asia-anshan-regional-contest-onsite","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/2014-acmicpc-asia-anshan-regional-contest-onsite\/","title":{"rendered":"2014 ACM\/ICPC Asia Anshan Regional Contest Onsite"},"content":{"rendered":"

http:\/\/acmicpc.info\/archives\/1803<\/a><\/p>\n

Problem C. Coprime<\/h2>\n

Brief description: <\/h3>\n

\u7ed9\u51fa n \u4e2a\u4e92\u4e0d\u76f8\u540c\u7684\u6570\uff0c\u6c42\u6ee1\u8db3\u4ee5\u4e0b\u6761\u4ef6\u7684\u4e09\u5143\u65e0\u5e8f\u7ec4\u7684\u4e2a\u6570\uff1a\u8981\u4e48\u4e24\u4e24\u4e92\u8d28\u8981\u4e48\u4e24\u4e24\u4e0d\u4e92\u8d28\u3002<\/p>\n

Analysis: <\/h3>\n

\u3002\u3002\u3002\u540c http:\/\/blog.csdn.net\/cool_fires\/article\/details\/8681888<\/a><\/p>\n

\u7136\u540e\u7528\u5bb9\u65a5\u539f\u7406\u4f18\u5316\u4e0b\u5c31\u884c\u4e86\u3002\u3002\u3002\u3002\uff08\u7c7b\u4f3c\u7261\u4e39\u6c5f F<\/a> \u7684\u65b9\u6cd5\uff09<\/p>\n

\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\n\r\n\/\/\u83ab\u6bd4\u4e4c\u65af mu \u51fd\u6570\r\nconst int PMAX = 100001;\r\nVI P, M; bitset<PMAX> isC; int mu[PMAX], cc[PMAX];\r\nVI dd[PMAX];\r\n#define ii (i*P[j])\r\nvoid sieve(){\r\n    mu[1] = 1; FOR(i, 2, PMAX){\r\n        if (!isC[i]) P.PB(i),mu[i]=-1;\r\n        for (int j=0;j<SZ(P)&&ii<PMAX;++j){\r\n            isC[ii]=1;if (!(i%P[j])){\r\n                mu[ii] = 0;\r\n                break;\r\n            }\r\n            else{\r\n                mu[ii] = -mu[i];\r\n            }\r\n        }\r\n    }\r\n\r\n    FOR(i, 1, PMAX) if (mu[i]){\r\n        M.PB(i);\r\n        for (int j=i;j<PMAX;j+=i) dd[j].PB(i);\r\n    }\r\n}\r\n#undef ii\r\n\r\nconst int N = int(1e5) + 9;\r\nint a[N];\r\nint n;\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n    sieve();\r\n\r\n    Rush{\r\n        RST(cc); REP_C(i, RD(n)){\r\n            RD(a[i]); ECH(d, dd[a[i]]) ++cc[*d];\r\n        }\r\n        LL z = 0; REP(i, n){\r\n            int c0 = 0; ECH(d, dd[a[i]]) c0 += mu[*d]*(cc[*d]-1);\r\n            z += (LL)c0*(n-1-c0);\r\n        }\r\n        OT((LL)n*(n-1)*(n-2)\/6-z\/2);\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/acmicpc.info\/archives\/1803 Problem C. Coprime Brief description: \u7ed9\u51fa n \u4e2a\u4e92\u4e0d\u76f8\u540c\u7684\u6570\uff0c\u6c42\u6ee1\u8db3\u4ee5\u4e0b\u6761\u4ef6\u7684\u4e09\u5143\u65e0\u5e8f\u7ec4\u7684\u4e2a\u6570\uff1a\u8981\u4e48\u4e24\u4e24\u4e92\u8d28\u8981\u4e48\u4e24\u4e24\u4e0d\u4e92\u8d28\u3002 Analysis: \u3002\u3002\u3002\u540c http:\/\/blog.csdn.net\/cool_fires\/article\/details\/8681888 \u7136\u540e\u7528\u5bb9\u65a5\u539f\u7406\u4f18\u5316\u4e0b\u5c31\u884c\u4e86\u3002\u3002\u3002\u3002\uff08\u7c7b\u4f3c\u7261\u4e39\u6c5f F \u7684\u65b9\u6cd5\uff09 \/\/}\/* …………………………………………………………………………………………………………………. *\/ \/\/\u83ab\u6bd4\u4e4c\u65af mu \u51fd\u6570 const int PMAX = 100001; VI P, M; bitset<PMAX> isC; int mu[PMAX], cc[PMAX]; VI dd[PMAX]; #define ii (i*P[j]) void sieve(){ mu[1] = 1; FOR(i, 2, PMAX){ if (!isC[i]) P.PB(i),mu[i]=-1; for (int j=0;j<SZ(P)&&ii<PMAX;++j){ isC[ii]=1;if (!(i%P[j])){ […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-1046","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-gS","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1046","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1046"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1046\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1046"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1046"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1046"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}