「算法笔记」莫比乌斯反演

莫比乌斯反演是数论中的重要内容。对于一些函数,如果很难直接求出它的值,而容易求出其倍数和或约数和,那么可以通过莫比乌斯反演求得原函数的值。


积性函数

定义

若 $\gcd(x,y) = 1$ 且 $f(xy) = f(x) f(y)$,则 $f(n)$ 为积性函数。

性质

若 $f(x)$ 和 $g(x)$ 均为积性函数,则以下函数也为积性函数:

$$ \begin{align*} h(x) & = f(x^p) \\ h(x) & = f^p(x) \\ h(x) & = f(x)g(x) \\ h(x) & = \sum_{d \mid x} f(d)g(\frac{x}{d}) \\ \end{align*} $$

例子

$$ \begin{array}{} \text{约数个数函数} & d(n)=\sum_{d\mid n}1 \\ \text{约数和函数} & \sigma(n)=\sum_{d\mid n}d \\ \text{约数}\ k\ \text{次幂函数} & \sigma_k(n)=\sum_{d\mid n}d^k \\ \text{欧拉函数} & \varphi(n)=\sum_{i=1}^n [\gcd(i,n)=1] \\ \text{莫比乌斯函数}& \mu(n)= \begin{cases} 1 & n=1 \\ (-1)^k & c_{1,2,\cdots,k}=1\quad(n=\prod_{i=1}^k {p_i}^{c_i}) \\ 0 & c_i>1 \end{cases} \end{array} $$


Dirichlet 卷积

定义

定义两个数论函数 $f,g$ 的 $\text{Dirichlet}$ 卷积为

$$ (f\ast g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d}) $$

性质

$\text{Dirichlet}$ 卷积满足交换律、结合律、分配律。

其中 $\varepsilon$ 为 $\text{Dirichlet}$ 卷积的单位元(任何函数卷 $\varepsilon$ 都为其本身)

例子

$$ \begin{align*} \varepsilon=\mu\ast 1 & \Leftrightarrow\varepsilon(n)=\sum_{d\mid n}\mu(d) \\ d=1\ast 1 & \Leftrightarrow d(n)=\sum_{d\mid n}1 \\ \sigma=d\ast 1 & \Leftrightarrow\varepsilon(n)=\sum_{d\mid n}d \\ \varphi=\mu\ast\operatorname{ID} & \Leftrightarrow\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d}) \\ \end{align*} $$


莫比乌斯函数

定义

$\mu$ 为莫比乌斯函数

性质

莫比乌斯函数不但是积性函数,还有如下性质:

$$ \mu(n)= \begin{cases} 1 & n=1 \\ 0 & n\ \text{含有平方因子} \\ (-1)^k & k\ \text{为}\ n\ \text{的本质不同质因子个数} \\ \end{cases} $$

证明

$$ \varepsilon(n)= \begin{cases} 1 & n=1 \\ 0 & n\neq 1 \\ \end{cases} $$

其中 $\varepsilon(n)=\sum_{d\mid n}\mu(d)$ 即 $\varepsilon=\mu\ast 1$

$$ n=\prod_{i=1}^k{p_i}^{c_i},n'=\prod_{i=1}^k p_i $$

那么

$$ \sum_{d\mid n}\mu(d)=\sum_{d\mid n'}\mu(d)=\sum_{i=0}^k C_k^i\cdot(-1)^k $$

根据二项式定理,易知该式子的值在 $k=0$ 即 $n=1$ 时值为 $1$ 否则为 $0$,这也同时证明了 $\sum_{d\mid n}\mu(d)=[n=1]$

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

  • 直接推导:如果 $\gcd(i,j)=1$,那么意味着上述结论中的 $n=1$,也就是式子的值是 $1$。反之不满足 $[\gcd(i,j)=1] $,值即为 $0$
  • 利用 $\varepsilon$ 函数:根据上一结论,$[\gcd(i,j)=1]\Rightarrow\varepsilon(\gcd(i,j))$,将 $\varepsilon$ 展开即可。

线性筛

由于 $\mu$ 函数为积性函数,因此可以线性筛莫比乌斯函数(线性筛基本可以求所有的积性函数,尽管方法不尽相同)。

代码

void sieve() {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!flg[i]) {
            p[++tot] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= tot && i * p[j] <= n; j++) {
            flg[i * p[j]] = true;
            if (i % p[j] == 0) {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
}

扩展结论

$$ \varphi\ast 1=\operatorname{ID}\quad\operatorname{ID}\ \text{即}\ f(x)=x $$

将 $n$ 分解质因数:$n=\prod_{i=1}^k {p_i}^{c_i}$

首先,因为 $\varphi$ 是积性函数,故只要证明当 $n'=p^c$ 时 $\varphi\ast 1=\sum_{d\mid n'}\varphi(\frac{n'}{d})=\operatorname{ID}$ 成立即可。

因为 $p$ 是质数,于是 $d=p^0,p^1,p^2,\cdots,p^c$

易知如下过程:

$$ \begin{align*} \varphi\ast 1 & =\sum_{d\mid n}\varphi(\frac{n}{d}) \\ & =\sum_{i=0}^c\varphi(p^i) \\ & =1+p^0\cdot(p-1)+p^1\cdot(p-1)+\cdots+p^{c-1}\cdot(p-1) \\ & =p^c \\ & =\operatorname{ID} \\ \end{align*} $$

该式子两侧同时卷 $\mu$ 可得 $\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d})$


莫比乌斯反演

公式

设 $f(n),g(n)$ 为两个数论函数。

如果有

$$ f(n)=\sum_{d\mid n}g(d) $$

那么有

$$ g(n)=\sum_{d\mid n}\mu(d)f(\frac{n}{d}) $$

证明

暴力计算

$$ \sum_{d\mid n}\mu(d)f(\frac{n}{d})=\sum_{d\mid n}\mu(d)\sum_{k\mid \frac{n}{d}}g(k)=\sum_{k\mid n}g(k)\sum_{d\mid \frac{n}{k}}\mu(d)=g(n) $$

用 $\sum_{d\mid n}g(d)$ 来替换 $f(\frac{n}{d})$,再变换求和顺序。最后一步转为的依据:$\sum_{d\mid n}\mu(d)=[n=1]$,因此在 $\frac{n}{k}=1$ 时第二个和式的值才为 $1$。此时 $n=k$,故原式等价于 $\sum_{k\mid n}[n=k]\cdot g(k)=g(n)$

运用卷积

原问题即为:已知 $f=g\ast 1$,证明 $g=f\ast\mu$

易知如下转化:$f\ast\mu=g\ast 1\ast\mu\Rightarrow f\ast\mu=g$(其中 $1\ast\mu=\varepsilon$)


习题

求解内容题目
$\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]$「HAOI 2011」Problem B
$\sum_{i=1}^n\operatorname{lcm}(i,n)$「SPOJ 5971」LCMSUM
$\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)$「BZOJ 2154」Crash 的数字表格
$\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c d(ijk)$「Codeforces 235E」Number Challenge
维护数组 $a$,支持对所有 $\gcd(x,n)=d$ 的 $a_x$ 增加相同的值和前缀和查询「HDU 4947」GCD Array

发表评论