初等数论学习笔记 III：数论函数与筛法( 十 ) _生活百科

复杂度分析：由递推式可知求解 \(s(n)\) 的复杂度为 \(n\) 的所有整除值的根号和。考虑 \(> \sqrt n\) 的整除值的贡献，即 \(\sum\limits_{d = 1} ^ {\sqrt n} \sqrt {\frac n d}\) 。\(\int \sqrt{n} x ^ {-\frac 1 2} dx = 2\sqrt n x ^ {\frac 1 2}\)，将 \(x = \sqrt n\) 带入，得 \(2n ^ {\frac 3 4}\) 。而小于 \(\sqrt n\) 的整除值的贡献为 \(\sum\limits_{d = 1} ^ {\sqrt n} \sqrt d\) 。\(\int \sqrt x dx = \frac 2 3 x ^ {\frac 3 2}\)，将 \(x = \sqrt n\) 带入，得 \(\frac 2 3 n ^ {\frac 3 4}\) 。因此总复杂度为 \(\mathcal{O}(n ^ {\frac 3 4})\) 。
在复杂度分析过程中我们还得到了一个有趣的结论：大于 \(\sqrt n\) 和小于 \(\sqrt n\) 的整除值的根号和级别相等。对于笔者而言，这个结论出乎意料。
一般预处理 \(f\) 及其前缀和到 \(n ^ {\frac 2 3}\) 处，复杂度优化为 \(n ^ {\frac 2 3} + \sqrt n (n ^ {\frac 1 3}) ^ {\frac 1 2} = \mathcal{O}(n ^ {\frac 2 3})\) 。
6.2 例题I. P4213 【模板】杜教筛（Sum）#include <bits/stdc++.h>using namespace std;using ll = long long;constexpr int N = 5e6 + 5;bool vis[N];int cnt, pr[N], mu[N], phi[N], smu[N];ll sphi[N];unordered_map<int, ll> p, m;ll dp(int n) {if(n < N) return sphi[n];auto it = p.find(n);if(it != p.end()) return it->second;ll sum = 1ll * n * (n + 1ll) / 2;for(int l = 2, r; ; l = r + 1) {r = n / (n / l);sum -= (r - l + 1) * dp(n / l);if(r == n) break;}return p[n] = sum;}int dm(int n) {if(n < N) return smu[n];auto it = m.find(n);if(it != m.end()) return it->second;ll sum = 1;for(int l = 2, r; l <= n; l = r + 1) {r = n / (n / l);sum -= (r - l + 1) * dm(n / l);if(r == n) break;}return m[n] = sum;}int main() {mu[1] = phi[1] = 1;for(int i = 2; i < N; i++) {if(!vis[i]) pr[++cnt] = i, mu[i] = -1, phi[i] = i - 1;for(int j = 1; j <= cnt && i * pr[j] < N; j++) {vis[i * pr[j]] = 1;if(i % pr[j] == 0) {phi[i * pr[j]] = phi[i] * pr[j];break;}phi[i * pr[j]] = phi[i] * (pr[j] - 1);mu[i * pr[j]] = -mu[i];}}for(int i = 1; i < N; i++) smu[i] = smu[i - 1] + mu[i], sphi[i] = sphi[i - 1] + phi[i];int T, n;cin >> T;while(T--) {cin >> n;cout << dp(n) << " " << dm(n) << "\n";}return 0;}参考文章第一章：