PE 521 \u6c42\u6700\u5c0f\u7d20\u56e0\u5b50\u524d\u7f00\u548c<\/a>\uff0c\u867d\u7136\u4e0d\u662f\u79ef\u6027\u51fd\u6570\uff0c\u4f46\u4e0d\u59a8\u788d\u6211\u4eec\u7b5b\u3002<\/p>\n\u4ee4 S(n, k) \u8868\u793a\u6b21\u5c0f\u8d28\u56e0\u5b50 >= P[k] \u65f6\u7684\u524d\u7f00\u548c\uff08P[0] = 0)\u3002
\n\u8f6c\u79fb\uff0c\u5206\u4e24\u79cd\u60c5\u51b5\uff1a
\n1. \u5269\u4f59\u90e8\u5206\u662f\u4e00\u4e2a\u66f4\u5927\u7684\u7d20\u6570\uff0c\u8d21\u732e\u662f\uff0cp * (g[id(n)] – g[p])\u3002
\n2. \u679a\u4e3e\u6700\u5c0f\u56e0\u5b50\u5206\u89e3\uff0c\u9012\u5f52\u3002<\/p>\n
\n#include <lastweapon\/io>\nusing namespace std;\n\nconst int N = int(1e6) + 9;\nLL n; int nn; int P[N], Pn;\nLL di[N], g[N]; int dn;\ninline int id(LL x) {return x <= nn ? x : dn-n\/x+1;}\n\nLL S(LL n, int k) {\n int p = P[k]; if (n <= p) return 0;\n LL z = p * (g[id(n)] - g[p]);\n FOR_1(i, k+1, Pn) {\n LL p = P[i]; if (p*p > n) break;\n for (LL j=n\/p;j>=p;j\/=p) {\n z += S(j, i) + p;\n }\n }\n return z;\n}\n\nLL S(LL n) {\n ::n = n; nn = sqrt(n); Pn = dn = 0;\n for (LL i=1,j;i<=n;i=j+1) {\n di[++dn] = j = n\/(n\/i);\n g[dn] = j-1;\n }\n FOR_1(p, 2, nn) if (g[p] != g[p-1]) {\n P[++Pn] = p; for (LL i=dn,ii=di[i];(LL)p*p<=ii;ii=di[--i]) {\n g[i] -= g[id(ii\/p)] - g[p-1];\n }\n }\n if (!Pn) return 0;\n return S(n, 0);\n}\n\nint main(){\n LL l, r; RD(l, r);\n cout << S(r) - S(l-1) << endl;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"\u9898\u610f\uff1a\u6b21\u5c0f\u7d20\u56e0\u5b50\u524d\u7f00\u548c\u3002 \u7c7b\u4f3c PE 521 \u6c42\u6700\u5c0f\u7d20\u56e0\u5b50\u524d\u7f00\u548c\uff0c\u867d\u7136\u4e0d\u662f\u79ef\u6027\u51fd\u6570\uff0c\u4f46\u4e0d\u59a8\u788d\u6211\u4eec\u7b5b\u3002 \u4ee4 S(n, k) \u8868\u793a\u6b21\u5c0f\u8d28\u56e0\u5b50 >= P[k] \u65f6\u7684\u524d\u7f00\u548c\uff08P[0] = 0)\u3002 \u8f6c\u79fb\uff0c\u5206\u4e24\u79cd\u60c5\u51b5\uff1a 1. \u5269\u4f59\u90e8\u5206\u662f\u4e00\u4e2a\u66f4\u5927\u7684\u7d20\u6570\uff0c\u8d21\u732e\u662f\uff0cp * (g[id(n)] – g[p])\u3002 2. \u679a\u4e3e\u6700\u5c0f\u56e0\u5b50\u5206\u89e3\uff0c\u9012\u5f52\u3002 #include <lastweapon\/io> using namespace std; const int N = int(1e6) + 9; LL n; int nn; int P[N], Pn; LL di[N], g[N]; int dn; inline int id(LL x) {return x <= nn […]<\/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-3422","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-Tc","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3422","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=3422"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3422\/revisions"}],"predecessor-version":[{"id":3423,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3422\/revisions\/3423"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=3422"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=3422"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=3422"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}