{"id":170,"date":"2022-09-09T17:09:18","date_gmt":"2022-09-09T09:09:18","guid":{"rendered":"https:\/\/vite66.cn\/?p=170"},"modified":"2025-01-11T16:57:35","modified_gmt":"2025-01-11T08:57:35","slug":"min25%e7%ad%9b","status":"publish","type":"post","link":"https:\/\/vite66.cn\/?p=170","title":{"rendered":"Min25\u7b5b"},"content":{"rendered":"<p><a href=\"https:\/\/www.zhihu.com\/question\/29580448\/answer\/882461056\">\u7406\u8bba<\/a><br \/>\n\u6a21\u677f<\/p>\n<pre><code>#define ll long long\n\ninline ll V2IDX(ll v, ll N, ll Ndr, ll nv) {\n    return v &gt;= Ndr ? (N\/v - 1) : (nv - v);\n}\n\nll primesum(ll N) {     \/\/\u6c42\u53d61~N\u7684\u6240\u6709\u8d28\u6570\u548c\n    ll *S;\n    ll *V;\n\n    ll r = (ll)sqrt(N);\n    ll Ndr = N\/r;\n\n    assert(r*r &lt;= N and (r+1)*(r+1) &gt; N);\n\n    ll nv = r + Ndr - 1;\n\n    V = new ll[nv];\n    S = new ll[nv];\n\n    for (ll i=0; i&lt;r; i++) {\n        V[i] = N\/(i+1);\n    }\n    for (ll i=r; i&lt;nv; i++) {\n        V[i] = V[i-1] - 1;\n    }\n\n    for (ll i=0; i&lt;nv; i++) {\n        S[i] = V[i] * (V[i] + 1) \/ 2 - 1;\n    }\n\n    for (ll p=2; p&lt;=r; p++) {\n        if (S[nv-p] &gt; S[nv-p+1]) {\n            ll sp = S[nv-p+1];\n            ll p2 = p*p;\n            for (ll i=0; i&lt;nv; i++) {\n                if (V[i] &gt;= p2) {\n                    S[i] -= p * (S[V2IDX(V[i]\/p, N, Ndr, nv)] - sp);\n                } else {\n                    break;\n                }\n            }\n        }\n    }\n\n    return S[0];\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u7406\u8bba \u6a21\u677f #define ll long long inline ll V2IDX(ll v, ll N,  [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[30],"class_list":["post-170","post","type-post","status-publish","format-standard","hentry","category-science-and-engineering","tag-30"],"_links":{"self":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/170","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=170"}],"version-history":[{"count":3,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/170\/revisions"}],"predecessor-version":[{"id":173,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/170\/revisions\/173"}],"wp:attachment":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=170"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=170"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}