莫比乌斯反演与狄利克雷卷积
终于算是搞明白这个东西了
一个记号:
艾弗森括号: $ [P]= \[\begin{cases}\ 1 &, P\ is\ true \\ 0 &, P\ is\ false \end{cases}\]false \end {cases} $ 其中 \(P\) 为一个命题, 同时艾弗森括号与其他值相乘时不受其定义域影响,例如 \(\frac{[x\neq 0]}{x}\) 当 \(x=0\) 时其值为零.
数论函数:
讲莫比乌斯反演首先得讲莫比乌斯函数, 讲莫比乌斯函数首先得说下啥是数论函数.
数论函数即是定义在正整数区间上的函数。常见的数论函数有欧拉 \(\varphi\) 函数,因数个数,因数和, 以及接下来讨论的莫比乌斯 \(\mu\) 函数.
一类比较重要的数论函数叫做积性函数: 对于两个互质的正整数 \(p,q\), 若有 \(f(pq)=f(p)f(q)\), 则称数论函数 \(f\) 为积性函数. 上面提到的数论函数都是积性函数.
特殊地,若去掉互质的约束,即对于任意正整数 \(p,q\) 均有 \(f(pq)=f(p)f(q)\), 则称 \(f\) 为完全积性函数. 比如 \(f(x) = x^k\).
积性函数都可以使用欧拉筛进行线性的预处理.
莫比乌斯函数:
莫比乌斯 \(\mu\) 函数的定义如下:
\[ \mu(x) = \begin{cases} 1 &, x=1 \\ (-1)^k &,x=\prod_{i=1}^k p_i \\ 0 &, others \end{cases} \] 其中 \(p_1 \neq p_2 \neq \cdots\), 且 \(p_i\) 均为质数.
一个重要性质如下:
\[ \sum_{d|n} \mu(d) = [n=1] \]
(事实上这个性质比反演好用)
证明:
当 \(n=1\) 时,等式显然成立.
当 \(n \neq 1\) 时,令 \(n = \prod_{i=1}^k p_i^{c_i}\)(质因数分解), 则有:
\[ \begin{aligned} & \sum_{d|n}\mu(d) \\ = & \ \mu(1) + \mu(p_1)+\mu(p_2)+\cdots \\ & + \mu(p_1p_2) + \mu(p_1p_3) + \cdots \\ & + \cdots + \mu(p_1p_2 \cdots p_k) \\ = & \ \sum_{i=0}^k (-1)^i {k \choose i} \\ = & \ (1-1)^k = 0 \end{aligned} \]
从中可以看出 \(\mu\) 函数在容斥当中的作用.
莫比乌斯反演:
对于函数 \(f(n)\), 若有 \(F(n) = \sum_{d|n} f(x)\), 则有 \(f(n) = \sum_{d|n}\mu(d)F(n/d)\).
另一种更常用的形式如下:
对于函数 \(f(n)\), 若有 \(F(n) = \sum_{n|d} f(x)\), 则有 \(f(n) = \sum_{n|d}\mu(d/n)F(d)\).
证明:
对于第一种形式:
\[ \require{extpfeil} \begin{aligned} \sum_{d|n}\mu(d)F(\frac{n}{d}) = & \sum_{d|n}\mu(d)\sum_{q|(n/d)}f(q) \\ \xlongequal{q|n, dq|n} & \sum_{q|n}f(q)\sum_{d|(n/q)}\mu(d) \\ = & \sum_{q|n}f(q)[\frac{n}{q}=1] \\ = & f(n) \end{aligned} \]
对于第二种形式:
\[ \begin{aligned} \sum_{n|d}\mu(\frac{d}{n})F(d) = & \sum_{i=1} \mu(i)F(in) \\ = & \sum_{i=1}\mu(i)\sum_{j=1}f(ijn) \\ \xlongequal{T=ij} & \sum_{T=1}f(Tn)\sum_{i|T}\mu(i) \\ = & \sum_{T=1}f(Tn)[T=1] \\ = & f(n) \end{aligned} \]
狄利克雷卷积:
对于两个数论函数 \(f(x),g(x)\), 定义运算:
\[ (f*g)(x) = \sum_{d|x}f(d)g(\frac{x}{d}) \]
该运算称为狄利克雷卷积.
显然狄利克雷卷积满足交换律,结合律和分配律. (其实是懒得写证明了)
狄利克雷卷积有条重要的性质:两个积性函数卷积后依然是积性函数, 所以通过狄利克雷卷积得到的函数也可以使用欧拉筛线性预处理.
狄利克雷卷积有单位元 \(\epsilon(x) = [x=1]\).
有了狄利克雷卷积,之前提到的 \(\mu\) 函数的性质就可以表示为:
\[ \mu * I = \epsilon \]
其中 \(I(x)=1\). 也即 \(\mu\) 是 \(I\) 的逆元.
此时莫比乌斯反演的第一种形式也变得十分显然:
\[ \begin{aligned} & F = f*I \\ \therefore \ & F*\mu = f*I*\mu \\ & = f * \epsilon = f \end{aligned} \]
同时欧拉 \(\varphi\) 函数有一个与狄利克雷卷积有关的性质:
\[ \sum_{d|n} \varphi(d) = n \]
证明:
\[\begin {aligned} \sum_{d|n} \varphi (d) = & \sum_{d|n}\varphi (\frac {n}{d}) \\ = & \sum_{d|n}\sum_{i=1}^{n/d}[(i,\frac {n}{d}=1)] \\ = & \sum_{d|n}\sum_{i=1}^{n/d}[(id,n)=d] \\ \xlongequal {引入无关项} & \sum_{d|n}\sum_{i=1}^{n}[(i,n)=d] \\ \xlongequal {枚举 gcd} & n \end {aligned} \]
事实上有个更通用的做法:考察积性函数在质数幂次上的值:
\[ \begin{aligned} \sum_{d|p^k} \varphi(d) = & 1 + \sum_{i=1}^{k} p^i-p^{i-1} \\ = & p^k \\ \mathrm{assume}\ n = & \prod_{p} p^k \\ \Rightarrow\sum_{d|n} \varphi(d) = & \prod_{p} \sum_{d|p^k} \varphi(d) \\ = & \prod_{p} p^k = n \end{aligned} \]
同时:
\[ \begin{aligned} & \varphi * I = id \\ \Longrightarrow & \varphi = id * \mu \\ \iff & \varphi(x) = \sum_{d|x} \mu(d) \frac{x}{d} \\ \Longrightarrow & \frac{\varphi(x)}{x} = \sum_{d|x} \frac{\mu(d)}{d} \end{aligned} \]
这个式子简洁地将 \(\varphi\) 函数与 \(\mu\) 函数结合在了一起. (虽然好像暂时不知道有啥用)