https://projecteuler.net/problem=521

拆解成两个子问题，

• 小于等于 n 的素数之和。
• 小于等于 n 的合数的最小素因子之和。

回忆 PE 10，我们可以用 $$O(n^{3/4})$$ 的复杂度去统计小于等于 n 的素数的 k 次方和。
那么前者是 k=1，后者可以求 k=0 的时候顺便得到。（因此每次筛 p 过程中，dp[n] 的变化，就是所有最小素因子等于 p 的合数的个数。）

Int f(LL n){
    LL r = sqrt(n); vector<LL> V; REP_1(i, r+1) V.PB(n/i);
    int up = int(*V.rbegin()); DWN_1(i, up-1, 1) V.PB(i);

<pre><code>Int z = 0;

unordered_map&amp;lt;LL, LL&amp;gt; dp;

REP(i, V.size()){
    LL x = V[i];
    dp[x] = x-1;
}


FOR_1(p, 2, r+1) if (dp[p] &amp;gt; dp[p-1]){
    LL prev = dp[n];
    LL pp = (LL)p*p; for(auto v: V){
        if (v &amp;lt; pp) break;
        dp[v] -= (dp[v/p] - dp[p-1]);
    }
    z += Int(p) * Int(prev - dp[n]);
}
return z;
</code></pre>

}

Int g(LL n){
    LL r = sqrt(n); vector&lt;LL&gt; V; REP_1(i, r+1) V.PB(n/i);
    int up = int(*V.rbegin()); DWN_1(i, up-1, 1) V.PB(i);

<pre><code>unordered_map&amp;lt;LL, Int&amp;gt; dp;

REP(i, V.size()){
    LL x = V[i];
    if (x&amp;amp;1) dp[x] = Int(x) * Int((x+1)/2) - 1;
    else dp[x] = Int(x/2) * Int(x+1) - 1;
}

FOR_1(p, 2, r+1) if (dp[p] != dp[p-1]) {
    LL pp = (LL)p*p; for(auto v: V){
        if (v &amp;lt; pp) break;
        dp[v] -= Int(p)*(dp[v/p] - dp[p-1]);
    }
}
return dp[n];
</code></pre>

}

int main(){

#ifndef ONLINE_JUDGE
    freopen(&quot;/users/xiaodao/desktop/Exercise/in.txt&quot;, &quot;r&quot;, stdin);
    //freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);
#endif

<pre><code>LL n = 1e12;
cout &amp;lt;&amp;lt;  f(n)  + g(n) &amp;lt;&amp;lt; endl;

//44389811
</code></pre>

}

Posted by xiaodao
Category: PE