本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-22 16:45:48

狄利克雷卷积

$$ 定义常值函数I(n) = 1; \quad 线性函数id(n) = n;\quad 单位函数\epsilon(n) = [n=1] $$

$$ 狄利克雷卷积：h(n) = \sum_{d\mid n}f(d) g(\frac d n) $$ $$ 记作h = f * g，有如下性质： $$

1. 交换律 $fg = gf$
2. 结合律 $(fg)h = f(gh)$
3. 分配率 $f(g+h) = fg + f*h$
4. $fh = gh 的充要条件是f=g（h(1)\ne0）$
5. $若fg=h，h是积性函数的充要条件是f,g均为积性函数$ 证明如下： $$ 设两积性函数f(n),g(n)，且h = fg;整数a,b互质 $$ h(a) = \sum_{d\mid a}f(d)\cdot g(\frac a d)\quad h(b) = \sum_{d\mid b}f(d)\cdot g(\frac b d) $$ $$ h(a)h(b) = \sum_{d_1\mid a}f(d_1)\cdot g(\frac a {d_1})\times \sum_{d_2\mid b}f(d_2)\cdot g(\frac{b}{d_2}) $$ $$ = \sum_{d\mid ab}f(d)\cdot g(\frac {ab} d) = h(ab) $$

狄利克雷逆元

关于狄利克雷卷积，其有逆运算，称之为狄利克雷逆元，如下：

若有 $fg=h和f=hg^{-1}$，则有 $gg^{-1}=\epsilon$，即 $g$ 的狄利克雷逆元，记作 $g^{-1}$。$g^{-1}$ 的表达式如下：
因为有 $(fg)(n)=\epsilon(n)=\sum_{d\mid n}g(d)\cdot f(\frac n d)$，
首先 $f(1)\times g(1)=\epsilon(1)$，得 $g(1)=\frac{1}{f(1)}$
对于 $n>1$，可发现等式右边总有一个 $g(n)$，将其提出，得到 $g(n)f(1) + \sum_{d\mid n,d\ne n}g(d)f(\frac n d )=0$ ，变形得到： $$ g(n) = -\frac{1}{f(1)}\sum_{d\mid n,d\ne n}g(d)f(\frac n d) $$ $g$ 便是 $f$ 的狄利克雷逆元。

莫比乌斯函数

定义

莫比乌斯函数 $\mu$ 是一个积性函数，而且它对应任意质数的取值都为 $−1$，任意质数的高次幂的取值都为 $0$。

基于此，对于 $\mu(n)$，对 $n$ 进行质因数分解，得到 $$ n = \prod_{k=1}^s p_k^{a_k} $$ 对于 $n=1$，有 $\mu(1)=1$，
否则：$若 \exists a_k >1,则 \mu(n)=0;\quad 否则若\forall a_k=1,那么\mu(n)=(-1)^s$。

方程及性质

方程

思考上文所述狄利克雷逆元相关知识，求 $I^{-1}$（设 $I^{-1}=f$）：

对于 $n=1$，有 $f(1)=1$；
否则，有 $$ f(n)=-\sum_{d\mid n,d\ne n}f(d) $$ 此时可以发现，对于任意质数 $p$，$f(p)=−f(1)=−1$，而 $f(p^2)=−[f(1)+f(p)]=0$。
容易发现，$p$ 的其他高次幂也都会等于 $0$，因为它们都等于 $−[f(1)+f(p)]$，因为其他 $f(p^n)$ 项都直接等于 $0$ 而被约去了。

这个函数其实就是莫比乌斯函数，我们可以得到它的表达式（$n>1$）:

$$ \mu(n) = -\sum_{d\mid n,d\ne n}\mu(d) $$

性质

由于 $I$ 是积性函数，且任意积性函数的狄利克雷逆元都是积性函数，所以莫比乌斯函数 $\mu$ 也是积性函数。

因此我们可以得到几点性质： $$ \mu * I = \epsilon $$ $$ \phi * I = id $$ $$ id * \mu = id * I^{-1} = \phi $$

关于莫比乌斯函数，它在狄利克雷生成函数中，等价于黎曼函数 $\zeta$ 的倒数

利用欧拉筛求莫比乌斯函数

1. $\mu(1)=1$.
2. 当 $n$ 是质数时，$\mu(n)=-1$。
3. 当 $n$ 不是质数且因子 $i$ 中包含质数 $prime_j$ 时，说明 $n$ 有质数的高次幂作为因子，所以此时 $\mu(n)=0$。
4. 当 $n$ 不是质数且因子 $i$ 中不包含质数 $prime_j$ 时，说明 $i$ 与 $prime_j$ 互质；又因为莫比乌斯函数是积性函数，且第2条可以得到 $\mu(prime_j)=-1$，所以此时 $\mu(n)=-\mu(i)$。

由此 $O(n)$ 可以得到莫比乌斯函数的任意值。

莫比乌斯反演

反演结论 $$ \sum_{d\mid \gcd(i,j)}\mu(d) = [\gcd(i,j)=1] $$

题

1. P2522 莫比乌斯反演+整除分块解法 AC代码
2. SP5971 莫比乌斯反演+莫比乌斯函数关于狄利克雷卷积的性解法 AC代码

范德蒙德卷积

$$ \sum_{i=0}^{k} {n \choose i} {m \choose k-i}={n+m \choose k} $$