杜教筛能低于线性，关键在于利用恒等式将 $ s(n) $ 拆解为 $ o(\sqrt{n}) $ 个不同 $ s(\lfloor n/k \rfloor) $ 子问题，结合记忆化哈希表避免重复计算，并预处理前 $ n^{2/3} $ 项，使总时间复杂度降至 $ o(n^{2/3}) $。
杜教筛为什么能低于线性？关键在整除分块 + 记忆化
杜教筛不是“凭空低于线性”，而是把求 S(n) = Σ_{i=1}^n f(i) 的问题，通过恒等式拆成若干个 S(⌊n/k⌋) 的子问题。由于 ⌊n/k⌋ 只有 O(√n) 个不同取值，再配合哈希表记忆化已算过的 S(m)，总状态数被压到 O(n^{2/3})（合理实现下）。不记忆化就退化成指数级，这点很多人一开始没意识到。
常见错误是直接递归不判重——比如反复计算 S(1000) 十几次；或者用 vector 下标存 S(m)，结果 m 动辄上亿，内存炸穿。
- 必须用
unordered_map<long long ll></long>或类似结构缓存S(m) - 预处理前
n^{2/3}项的前缀和（通常取B = max(2000000, (int)pow(n, 2.0/3))），避免小值也递归 - 递归入口加判：若
m ，直接查预处理数组，不进递归
怎么选辅助函数 g？看 f * g 是否易求前缀和
杜教筛核心公式是：(f * g)(n) = Σ_{d|n} f(d) g(n/d)，然后推得：g(1)S(n) = Σ_{i=1}^n (f*g)(i) − Σ_{i=2}^n g(i) S(⌊n/i⌋)。所以 g 不是随便选的，它要满足两个条件：一是 g 自身前缀和好算，二是卷积 f * g 的前缀和更好算。
例如求 μ 前缀和（莫比乌斯函数）：选 g = 1（常函数），因为 μ * 1 = ε（单位函数），而 Σ_{i=1}^n ε(i) = 1，右边第一项就是常数；g(i)=1 的前缀和也是 i，简单。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
-
f = φ（欧拉函数）：选g = 1，因为φ * 1 = id，Σ id(i) = n(n+1)/2 -
f = μ²（平方因子自由数）：选g = μ，因为μ² * μ = μ，而Σ μ(i)正是你要算的，不行；实际常用g = 1，因μ² * 1 = 2^ω(n)不够好；更稳的是用μ² = |μ| = Σ_{d²|n} μ(d)转成枚举d，但这就不是标准杜教筛了——说明不是所有函数都适合硬套
递归实现里 ⌊n/i⌋ 分块怎么写才不漏、不重、不慢？
别手写 for (int i = 1; i ，那是线性的。正确做法是枚举每个不同值 <code>v = ⌊n/i⌋ 对应的区间 [l, r]，其中 r = n / (n / l)。这个公式本身没问题，但边界容易错：当 n 很大（如 1e12）时，int 会溢出，必须全程用 long long；另外 l 从 2 开始（因为 g(1)S(n) 单独提出来了），且要确保 r >= l。
典型错误是写成 for (ll l = 2, r; l 却忘了更新 <code>r，或者用 double 算 n/l 引入浮点误差。
- 务必用
ll r = n / (n / l);，且n / l是整除，不会出错 - 循环内先算
ll v = n / l;，再用S(v)递归，别重复算n/l - 如果
v ，直接取预处理值；否则递归调用，但递归前检查 map 里有没有
为什么跑得还是慢？三个隐蔽开销常被忽略
理论复杂度漂亮，实测卡在 1e11 就 TLE？大概率栽在这三处：
-
unordered_map插入和查询均摊O(1)，但常数极大；换成gp_hash_table（GCC 扩展）或手写哈希表能快 2–3 倍；或者用 vector + 链地址法，但要注意内存分配策略 - 预处理数组大小设太小（比如只预处理到
1e6），导致大量小m还走递归；设到2e6 ~ 5e6更稳 - 没有剪枝：当
n == 1时直接返回f(1)；当n == 0返回 0；这些基础 case 不判，栈深度无谓增加
最麻烦的是不同 f 对应的最优参数（预处理量、哈希策略、是否用迭代代替递归）都不一样，没法一套代码打天下。调试时建议先用 n = 1e6 打印所有递归进入的 m 值，看是不是集中在某几个数量级——如果是，说明分块或记忆化没生效。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
