【初学】杜教筛
杜教筛用于求解积性函数的前缀和。
定义函数：\(\epsilon(i)=[i=1],I(i)=1,id(i)=i\)。
狄利克雷卷积
\((f*g)(n)=f(n)*g(n)=\sum\limits_{ij=n} f(i)g(j)\)
-
交换律：\(f*g=g*f\)，显然。
-
结合律：\((f*g)*h=f*(g*h)\)。
结合律证明：
\(((f*g)*h)(n)=\sum\limits_{ij=n}(f*g)(i)h(j)=\sum\limits_{ij=n}(\sum\limits_{pq=i}f(p)g(q))h(j)=\sum\limits_{ijk=n}f(i)g(j)h(k)\)
\((f*(g*h))(n)=\sum\limits_{ij=n}f(i)(g*h)(j)=\sum\limits_{ij=n}f(i)(\sum\limits_{pq=j}g(p)h(q))=\sum\limits_{ijk=n}f(i)g(j)h(k)\)
-
单位元：\(\epsilon\) ，\(\epsilon*f=f\)。
\((\epsilon*f)(n)=\sum\limits_{ij=n}\epsilon(i)f(j)=f(n)\)
故 \(\epsilon*f=f\)。
莫比乌斯函数
称 \(I\) 在狄利克雷卷积意义下的逆元为莫比乌斯函数 \(\mu\)。
由狄利克雷卷积的定义式得：\(I*\mu=\epsilon\Rightarrow\sum\limits_{d|n}\mu(d)=\epsilon(n)\)。
因此，得到：\(\mu(n)=\begin{cases} 1, & n=1\\ (-1)^k, & n\text{能写成}k\text{个不同质数之积}\\ 0, & n\text{有完全平方数因子} \end{cases}\)
证明：
-
当 \(n=1\) 时，\(\mu(1)=\epsilon(1)=1\)。
-
当 \(n\neq 1\) 时，由唯一分解定理得：\(n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots p_k^{a_k}\)。
\(\sum\limits_{d|n}\mu(d)=\mu(1)+\mu(p_1)+\mu(p_2)+\mu(p_3)+\dots+\mu(p_k)+\mu(p_1p_2)+\dots+\mu(p_1p_2p_3\dots p_k)\)
\(\Rightarrow \sum\limits_{d|n}\mu(d)=\sum\limits_{i=0}^k C_k^i(-1)^i=0\)。
部分函数的狄利克雷卷积性质
-
\(I*\mu=\epsilon\)。
证明见莫比乌斯函数部分。
-
\(\varphi*I=id\)。
证明：要证 \(\varphi*I=id\)，只需证 \(\sum\limits_{d|n}\varphi(d)=n\)。
设 \(f(n)=\sum\limits_{d|n}\varphi(d)\)。则若 \(n,m\) 互质，则 \(f(nm)=\sum\limits_{d|nm}\varphi(d)=(\sum\limits_{d|n}\varphi(d))(\sum\limits_{d|m}\varphi(m))=f(n)f(m)\)。
因此 \(f\) 是积性函数。
\(f(p^a)=\sum\limits_{d|p^a}\varphi(d)=\varphi(1)+\varphi(p)+\varphi(p^2)+\dots+\varphi(p^a)=p^a\)。
令 \(n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots p_k^{a_k}\)，则 \(f(n)=\prod\limits_{i=1}^k f(p_i^{a_i})=\prod\limits_{i=1}^kp_i^{a_i}=n\)。故\(\sum\limits_{d|n}\varphi(d)=n\)。
-
\(\mu*id=\varphi\)。
由性质 1 与 2，得 \(I*\mu*id=\epsilon*\varphi*I\)，故 \(\mu*id=\epsilon*\varphi=\varphi\)。
莫比乌斯反演
若 \(f(n)=\sum\limits_{d|n}g(d)=\sum\limits_{d|n}g(\frac{n}{d})\)，则有 \(g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d})=\sum\limits_{d|n}\mu(\frac{n}{d})f(d)\)。
证明：原命题等价于 \(f=g*I \Leftrightarrow g=f*\mu\)。
\(f=g*I\Rightarrow f*\mu=(g*I)*\mu\Rightarrow f*\mu=g*(I*\mu)\Rightarrow f*u=g*\epsilon\Rightarrow f*\mu=g\)
反之亦然。
杜教筛
令 \(S(n)=\sum\limits_{i=1}^nf(i)\)，注意 \(f\) 为积性函数。
寻找另一个合适的积性函数 \(g\)，得到 \(\sum\limits_{i=1}^n(f*g)(i)=\sum\limits_{i=1}^n\sum\limits_{pq=i}f(p)g(q)=\sum\limits_{i=1}^n\sum\limits_{d|i}f(d)g(\frac{n}{d})=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}f(i)=\sum\limits_{d=1}^ng(d)S(\left\lfloor\frac{n}{d}\rfloor\right)\)。
则 \(S(n)g(1)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{i=2}^ng(i)S(\left\lfloor\frac{n}{i}\rfloor\right)\)。
若能快速求解 \(f*g\) 的前缀和与 \(g\) 的前缀和，则用数论分块的方法即可在 \(O(n^{\frac{3}{4}})\) 复杂度内求解 \(f\) 的前缀和。
复杂度证明：令 \(T(n)\) 为求解 \(S(n)\) 的复杂度。
\(T(n)=\sum\limits_{i=1}^{\sqrt n}(T(\frac{n}{i})+T(i))\)。前半部分为递归求解复杂度，后半部分为数论分块复杂度。
可以认为 \(T(n)=\sum\limits_{i=1}^{\sqrt n}(\sqrt i+\sqrt{\frac{n}{i}})\)，显然 \(i\le \frac{n}{i}\)，故忽略 \(\sqrt i\) 的项，得到 \(T(n)=\sum\limits_{i=1}^{\sqrt n} \sqrt{\frac{n}{i}}\le\int_1^{\sqrt n} \frac{\sqrt{n}}{\sqrt{x}}=2\sqrt n\sqrt{\sqrt n}=O(n^{\frac{3}{4}})\)。
为降低杜教筛复杂度，我们先用线性筛预处理前 \(n^t\) 个函数前缀和值，积分式变为：\(\int_1^{n^{1-t}}\frac{\sqrt{n}}{\sqrt{x}}=O(n^{1-0.5t})\)。
当 \(n^t=n^{1-0.5t}\) 时复杂度最优，则 \(t=\frac{2}{3}\)，杜教筛复杂度为 \(O(n^{\frac{2}{3}})\)。