反演

杜教筛

杜教筛用于求解积性函数的前缀和。

定义函数：$\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)$

1. 交换律：$f*g=g*f$，显然。

2. 结合律：$(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)$

3. 单位元：$\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}$

证明：

1. 当 $n=1$ 时，$\mu(1)=\epsilon(1)=1$。

2. 当 $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$。

部分函数的狄利克雷卷积性质

1. $I*\mu=\epsilon$。

   证明见莫比乌斯函数部分。

2. $\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$。

3. $\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}})$。