{"id":1149,"date":"2015-07-06T00:33:33","date_gmt":"2015-07-05T16:33:33","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1149"},"modified":"2015-07-11T10:19:55","modified_gmt":"2015-07-11T02:19:55","slug":"project-euler-501-eight-divisors","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/project-euler-501-eight-divisors\/","title":{"rendered":"Project Euler 501. Eight Divisors"},"content":{"rendered":"<p><!--more--><br \/>\n<a href=\"https:\/\/projecteuler.net\/problem=501\">https:\/\/projecteuler.net\/problem=501<\/a><\/p>\n<hr>\n<p>\u5982\u4f55\u4e00\u6b21\u7b5b\u6cd5\u6c42\u51fa\u6240\u6709\u7684\u89e3\uff1f\u62c6\u6210\u4e24\u4e2a\u6570\u7ec4\uff0c\u5927\u5c0f\u90fd\u5c0f\u4e8e sqrt(n)\uff1a<\/p>\n<ul>\n<li>F[i]: \u5c0f\u4e8e\u7b49\u4e8e i \u7684 PrimePi\u3002<\/li>\n<li>G[i]: \u5c0f\u4e8e\u7b49\u4e8e n\/i \u7684 PrimePi\u3002<\/li>\n<\/ul>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int PMAX = 1000000 + 1;\r\nvector&lt;LL&gt; P; bitset&lt;PMAX&gt; isC;\r\nLL n, nn; int PP&#x5B;PMAX];\r\n\r\nbool isPrime(LL x){\r\n    ECH(it, P){\r\n        if (sqr(*it) &gt; x) break;\r\n        if (x % *it == 0) return false;\r\n    }\r\n    return true;\r\n}\r\n\r\n#define ii (i*P&#x5B;j])\r\n#include &lt;unordered_map&gt;\r\nunordered_map&lt;LL, LL&gt; F, G;\r\n\r\nvoid sieve(){\r\n    \r\n    nn = sqrt(n); FOR(i, 2, nn+1){\r\n        if (!isC&#x5B;i]) P.PB(i);\r\n        for (int j=0;j&lt;SZ(P)&amp;&amp;ii&lt;nn;++j){\r\n            isC&#x5B;ii]=1; if (!(i%P&#x5B;j])) break;\r\n        }\r\n    }\r\n    \r\n    REP_1(i, nn+1){\r\n        F&#x5B;i] = i-1;\r\n        G&#x5B;i] = n\/i - 1;\r\n    }\r\n    \r\n    FOR_1(p, 2, nn+1) if (F&#x5B;p-1] != F&#x5B;p]){\r\n        LL pp = (LL) p * p;\r\n        LL up = min(nn, n \/ pp);\r\n        REP_1(q, up){\r\n            LL d = (LL)p * q;\r\n            if (d &lt;= nn) G&#x5B;q] -= G&#x5B;d] - F&#x5B;p-1];\r\n            else G&#x5B;q] -= F&#x5B;n\/d] - F&#x5B;p-1];\r\n        }\r\n        DWN_1(i, nn+1, pp-1) F&#x5B;i] -= F&#x5B;i\/p] - F&#x5B;p-1];\r\n    }\r\n}\r\n\r\nLL f(LL n){\r\n    LL r = sqrt(n); vector&lt;LL&gt; V; REP_1(i, r+1) V.PB(n\/i);\r\n    int up = int(*V.rbegin()); DWN_1(i, up-1, 1) V.PB(i);\r\n    \r\n    Int z = 0;\r\n    \r\n    unordered_map&lt;LL, LL&gt; dp;\r\n    \r\n    REP(i, V.size()){\r\n        LL x = V&#x5B;i];\r\n        dp&#x5B;x] = x-1;\r\n    }\r\n    \r\n    \r\n    FOR_1(p, 2, r+1) if (dp&#x5B;p] &gt; dp&#x5B;p-1]){\r\n        LL pp = (LL)p*p; for(auto v: V){\r\n            if (v &lt; pp) break;\r\n            dp&#x5B;v] -= (dp&#x5B;v\/p] - dp&#x5B;p-1]);\r\n        }\r\n    }\r\n    return dp&#x5B;n];\r\n}\r\n\r\n\r\nLL z = 0;\r\n\r\nint main(){\r\n    \r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;\/users\/xiaodao\/desktop\/Exercise\/in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/   freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n    \r\n    \r\n    n = 1e12; sieve(); z = 0;\r\n    \r\n    ECH(it, P){\r\n        if (pow(*it, 7) &gt; n) break;\r\n        z += 1;\r\n    }\r\n    \r\n    REP(i, P.size()){\r\n    \r\n        LL t = n \/ cub(P&#x5B;i]);  if (!t) break;\r\n        z += t &lt;= nn ? F&#x5B;t] : G&#x5B;cub(P&#x5B;i])];\r\n        if (t &gt;= P&#x5B;i]) z -= 1;\r\n        \r\n        FOR(j, i+1, P.size()){\r\n            LL x = P&#x5B;i] * P&#x5B;j];\r\n            if (n\/x &gt; P&#x5B;j]){\r\n                z += n\/x &lt;= nn ? F&#x5B;n\/x] : G&#x5B;x];\r\n                z -= j+1;\r\n            }\r\n            else break;\r\n        }\r\n    }\r\n    \r\n    cout &lt;&lt; z &lt;&lt; endl;\r\n}\r\n\/\/ 197912312715\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[143],"tags":[],"class_list":["post-1149","post","type-post","status-publish","format-standard","hentry","category-pe"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-ix","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1149","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=1149"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1149\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1149"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1149"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1149"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}