{"id":1141,"date":"2015-07-01T07:00:49","date_gmt":"2015-06-30T23:00:49","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1141"},"modified":"2015-07-11T07:27:08","modified_gmt":"2015-07-10T23:27:08","slug":"project-euler-516-5-smooth-totients","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/project-euler-516-5-smooth-totients\/","title":{"rendered":"Project Euler 516. 5-smooth totients"},"content":{"rendered":"<p><!--more--><br \/>\n<a href=\"https:\/\/projecteuler.net\/problem=516\">https:\/\/projecteuler.net\/problem=516<\/a><\/p>\n<hr>\n<p>\u3002\u3002\u89c2\u5bdf\u7b26\u5408\u6761\u4ef6\u7684\u539f\u6570 x \u7684 Pattern\u3002\u3002<br \/>\n\u663e\u7136\u5f62\u5982<br \/>\n x = p1p2p3&#8230;pn2^a3^b5^c<br \/>\n\u4e14 pi =  2^d3^e^5^f + 1<br \/>\n\u3002\u3002\u3002 <\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\r\nconst int PMAX = 1000000;\r\nVI P; bitset&lt;PMAX&gt; isC;\r\n#define ii (i*P&#x5B;j])\r\nvoid sieve(){\r\n    FOR(i, 2, PMAX){\r\n        if (!isC&#x5B;i]) P.PB(i);\r\n        for (int j=0;j&lt;SZ(P)&amp;&amp;ii&lt;PMAX;++j){\r\n            isC&#x5B;ii]=1; if (!(i%P&#x5B;j])) break;\r\n        }\r\n    }\r\n}\r\n#undef ii\r\n\r\n\r\ninline bool isPrime(LL n){\r\n    ECH(it, P){\r\n        if (*it &gt;= n) return true;\r\n        if (n % *it == 0) return false;\r\n    }\r\n    return true;\r\n}\r\n\r\n\r\nvector&lt;LL&gt; PP, P235; LL n;\r\n\r\n\r\nvoid dfs1(int k = 0, LL n = 1){\r\n    if (k == 3){\r\n        P235.PB(n);\r\n        if (n+1 &gt; 5 &amp;&amp; n+1 &lt;= ::n &amp;&amp; isPrime(n+1)) PP.PB(n+1);\r\n    }\r\n    else{\r\n        do{\r\n            dfs1(k+1, n);\r\n            n *= P&#x5B;k];\r\n        } while (n &lt;= ::n);\r\n    }\r\n}\r\nuint z = 0;\r\n\r\n\r\nvoid dfs3(int k, LL n){\r\n    ECH(it, P235){\r\n        if ((double)*it * n &lt;= ::n){\r\n            z += *it * n;\r\n        }\r\n    }\r\n}\r\n\r\nvoid dfs2(int k = 0, LL n = 1){\r\n    if (k == PP.size()){\r\n        dfs3(0, n);\r\n    }\r\n    else{\r\n        dfs2(k+1, n);\r\n        if (n  &lt;= ::n \/ PP&#x5B;k] ) dfs2(k+1, n * PP&#x5B;k]);\r\n    }\r\n}\r\n\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;\/users\/xiaodao\/desktop\/Exercise\/out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    sieve(); n = 1e12;\r\n    dfs1(); SRT(PP); SRT(P235);    \r\n    dfs2();\r\n    cout &lt;&lt; z &lt;&lt; endl;\r\n    \r\n}\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":[144],"class_list":["post-1141","post","type-post","status-publish","format-standard","hentry","category-pe","tag-144"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-ip","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1141","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=1141"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1141\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1141"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1141"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1141"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}