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); Int z = 0; unordered_map<LL, LL> dp; REP(i, V.size()){ LL x = V[i]; dp[x] = x-1; } FOR_1(p, 2, r+1) if (dp[p] > dp[p-1]){ LL prev = dp[n]; LL pp = (LL)p*p; for(auto v: V){ if (v < pp) break; dp[v] -= (dp[v/p] - dp[p-1]); } z += Int(p) * Int(prev - dp[n]); } return z; } Int g(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); unordered_map<LL, Int> dp; REP(i, V.size()){ LL x = V[i]; if (x&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 < pp) break; dp[v] -= Int(p)*(dp[v/p] - dp[p-1]); } } return dp[n]; } int main(){ #ifndef ONLINE_JUDGE freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif LL n = 1e12; cout << f(n) + g(n) << endl; //44389811 }