杜教筛学习笔记
闲话
感觉以前根本没学懂杜教筛，于是重学了一遍，写个笔记记录一下。
前置知识
依赖于迪利克雷卷积、莫比乌斯反演、整除分块相关知识。
记号约定及基本性质
约定：
- \(f*g\) 表示 \(f\) 与 \(g\) 的迪利克雷卷积，即 \((f*g)(n)=\sum\limits_{ij=n}f(i)g(j)\)。
- \(f\cdot g\) 表示 \(f\) 与 \(g\) 的点积，即 \((f\cdot g)(n)=f(n)g(n)\)。
- \(f^k\) 表示 \(f\) 点积的幂次，即 \(f^k=\underbrace{f\cdot f\cdot\cdots\cdot f}_{k\textrm{ times}}\)。
- \(S_f\) 表示 \(f\) 的前缀和，即 \(S_f(n)=\sum\limits_{i=1}^nf(i)\)。
- \(\epsilon(x)=[x=1]\)。
- \(\operatorname{I}(x)=1\)。
- \(\operatorname{id}(x)=x\)。
- \(\varphi\) 为欧拉函数，即 \(\varphi(n)=\sum\limits_{i=1}^n[i\perp n]\)。
- \(\mu\) 为莫比乌斯函数，是 \(\operatorname{I}\) 的反函数，设 \(n=\prod_{i=1}^kp_i^{\alpha_i}\)，即 \(\mu(n)=\begin{cases}1,&n=1\\0,&\exists i,\alpha_i\ge 2\\(-1)^k,&\forall i,\alpha_i=1\end{cases}\)。
- \(\sigma_k\) 为因数幂和函数，即 \(\sigma_k(n)=\sum\limits_{d\mid n}d^k\)。特别地，\(\sigma_0\) 为因数个数函数，\(\sigma_1\) 为因数和函数。
有性质：
- \(\varphi*\operatorname{I}=\operatorname{id}\)，即 \(\varphi=\mu*\operatorname{id}\)。
- \(\mu*\operatorname{I}=\epsilon\)。
- \((f\cdot g)*(f\cdot h)=f\cdot(g*h)\)。
杜教筛算法流程
杜教筛用于求一类数论函数的前缀和，并不要求积性。
假设要求 \(S_f(n)\)，如果构造出数论函数 \(g\) 满足 \(S_g,S_h\) 可以快速求出（记 \(h=f*g\)），即可快速计算出 \(S_f(n)\)。
进行以下推导：
\[\begin{aligned}
S_h(n)&=\sum_{i=1}^nh(i)\\
&=\sum_{i=1}^n\sum_{d\mid i}f\left(\frac{i}{d}\right)g(d)\\
&=\sum_{d=1}^n\sum_{i=1}^{\frac{n}{d}}f(i)g(d)\\
&=\sum_{d=1}^ng(d)S_f\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\\
&=g(1)S_f(n)+\sum_{d=2}^ng(d)S_f\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\\
S_f(n)&=\frac{1}{g(1)}\left(S_h(n)-\sum_{d=2}^ng(d)S_f\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\right)
\end{aligned}
\]
利用可以快速求出的 \(S_h\) 和 \(S_g\)，可以整除分块求解。
复杂度证明
显然只会递归求 \(S_f\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\) 的值，共 \(O(\sqrt{n})\) 个，可以记忆化之。
复杂度为：
\[\begin{aligned}
T(n)&=O\left(\sum_{i=1}^{\sqrt{n}}T(i)\right)+O\left(\sum_{i=1}^{\sqrt{n}}T\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\right)\\
&=O\left(\sum_{i=1}^{\sqrt{n}}T\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\right)\\
&=O\left(\int_1^{\sqrt{n}}\sqrt{\frac{n}{x}}\textrm{d}x\right)\\
&=O\left(n^{\frac{3}{4}}\right)
\end{aligned}
\]
如果我们预处理出 \(1\sim n^c\) 的答案（其中 \(c > \frac{1}{2}\)），那么只需要递归计算 \(\lfloor\frac{n}{1}\rfloor,\lfloor\frac{n}{2}\rfloor,\cdots,\lfloor\frac{n}{n^{1-c}}\rfloor\)，复杂度为：
\[\begin{aligned}
T(n)&=O\left(n^c+\sum_{i=1}^{n^{1-c}}\sqrt{\left\lfloor\frac{n}{i}\right\rfloor}\right)\\
&=O\left(n^c+\int_1^{n^{1-c}}\sqrt{\frac{n}{x}}\textrm{d}x\right)\\
&=O\left(n^c+n^{1-\frac{1}{2}c}\right)\\
\end{aligned}
\]
令 \(c=\frac{2}{3}\) 时达到最优复杂度 \(T(n)=O(n^{\frac{2}{3}})\)。
记忆化时使用 map 的话多一个 \(\log\)，如果利用整除分块的性质在数组里记忆化，就不会带 \(\log\)。