算法

莫比乌斯反演及狄利克雷卷积速通

莫比乌斯反演速通

前言

由于请假错过了讲课，所以莫反是我第一个需要自学的难度不小的数学知识。

自学的过程的狼狈的，旁边也曾是自学的 czn 告诉我如果学会“狄利克雷卷积”就可以对“莫比乌斯反演”的理解进行“降维打击”。他还十分热心地带着我速通了一遍狄卷与莫反。

一知半解，就自学了很多资料。终于是补全了每一块知识碎片。

秉着造福后人的原则，我想写一篇非常非常通俗易懂的学习笔记。

易懂到什么程度呢？——就是初一的同学，也能速通。

食用指南：备好草稿纸，遇到式子先自己推导，培养推式子的习惯。

数论函数

这是狄利克雷卷积（后文简称“狄卷”）的前置知识。

数论函数是一类这样的函数：定义域为正整数，值域是一个数集。

数论函数间的简单运算有加法与数乘。

  • 加法：定义为两个函数逐位相加。$(f+g)(n)=f(n)+g(n)$
  • 数乘：定义为其函数每位都乘一个数。$(xf)(n)=x\cdot f(n)$

狄利克雷卷积

狄卷是数论函数间的运算，记为：

$$ f*g=h $$

等号左侧展开为：

$$ f*g=\sum\limits_{i|n}f(i)\cdot g(\frac{n}{i}) $$

一些运算律

交换律：$fg=gf$，这个显然。

结合律：$(fg)h=f(gh)$，因为：

$$ \sum\limits_{i\cdot j\cdot k=n}(f(i)g(j))\cdot h(k)=\sum\limits_{i\cdot j\cdot k=n}f(i)\cdot (g(j)h(k)) $$

分配律：$fh+gh=(f+g)*h$，因为：

$$ \begin{aligned} f*h+g*h&=\sum\limits_{i|n}f(i)h(\frac{n}{i})+\sum\limits_{i|n}g(i)h(\frac{n}{i})\\ &=\sum\limits_{i|n} f(i)h(\frac{n}{i})+g(i)h(\frac{n}{i})\\ &=\sum\limits_{i|n} (f(i)+g(i))\cdot h(\frac{n}{i})\\ &=\sum\limits_{i|n} (f+g)(i)\cdot h(\frac{n}{i})\\ &=(f+g)*h \end{aligned} $$

一些函数意义

  1. $\varphi(n)$：$[1,n]$ 中与 $n$ 互质的数的个数。 性质：$\varphi(1)=1$，$\varphi(n)=n-1$ 当且仅当 $n$ 为质数。

  2. $\mu(n)$：莫比乌斯函数。 定义：

    • $\mu(n)=1$，（$n=1$）
    • $\mu(n)=(-1)^k$，（$n=\prod\limits _{i=1}^{k} p_i$ 且 $p_i$ 为指数为 $1$ 的质数）
    • $\mu(n)=0$，（其他情况）

  3. $Id_k(n)$：幂函数，$Id_k(n)=n^k$。

  4. $\sigma_k(n)$：$n$ 的所有因数的 $k$ 次方和。

  5. $\epsilon(n)$：值为 $[n=1]$。即当且仅当 $n=1$ 时值为 $1$，否则为 $0$。

  6. $d(n)$：$n$ 的所有因数个数，即 $\sigma_0(n)$。

  7. $I(n)$：常函数，值恒为 $1$，即 $Id_0(n)$。

这里说明一下第七条，在一些参考书中写作 $\mathbf{1}(n)$，本文为了区分函数与常数，这里用 $I(n)$ 代替 $\mathbf{1}(n)$。

一些式子

这里会有很多公式，可以再看证明之前自己先证一遍，难度从易到难。

式子一：$(xf)g=x(fg)$，因为：

$$ \begin{aligned} (xf)*g&=\sum\limits_{i|n} (xf)(i)\cdot g(\frac{n}{i})\\ &=\sum\limits_{i|n} x\cdot f(i)\cdot g(\frac{n}{i})\\ &=x\cdot \sum\limits_{i|n} f(i)g(\frac{n}{i})\\ &=x(f*g) \end{aligned} $$

式子二：$f*\epsilon=f$，因为：

$$ \begin{aligned} (f*\epsilon) (n)&=\sum\limits_{i|n} f(i)\epsilon(\frac{n}{i})\\ &=f(n) \end{aligned} $$

式子三：$I*I=d$，因为：

$$ \begin{aligned} I*I&=\sum\limits_{i|n} I(i)I(\frac{n}{i})\\ &=\sum\limits_{i|n} 1\\ &=d \end{aligned} $$

式子四：$I*Id_k=\sigma_k$，因为：

$$ \begin{aligned} I*Id_k&=\sum\limits_{i|n} I(i)Id_k(\frac{n}{i})\\ &=\sum\limits_{i|n} Id_k(i)\\ &=\sigma_k \end{aligned} $$

式子五：$\mu*I=\epsilon$，因为：

$$ \begin{aligned} \mu*I&=\sum\limits_{i|n} \mu(i)I(\frac{n}{i})\\ &=\sum\limits_{i|n} \mu(i) \end{aligned} $$
  • 当 $n=1$，显然成立。
  • 当 $n\neq 1$，将 $n$ 分解为 $n=p_1^{m_1}p_2^{m_2}\dots p_k^{m_k}$。 计算有效的 $\mu$，肯定质因子的指数为 $1$。 所以每次在 $k$ 个质因数选择 $r$ 个，即 $C_k^r$ 个。 那就可以继续推式子了。
$$ \begin{aligned} \sum\limits_{i|n} \mu(i)&=C_k^0-C_k^1+C_k^2-C_k^3+\dots +(-1)^kC_k^k\\ &=\sum\limits_{i=0}^k (-1)^iC_k^i\\ &=(1-1)^k=0 \end{aligned} $$

因此，$\mu *I=\sum\limits_{i|n} \mu(i)=[n=1]=\epsilon$。

这里解释一下是怎么得到 $(1-1)^k$ 的：

二项式定理：$(x+y)^k=\sum\limits_{i=0}^k C_k^ix^{k-i}y^i$。

这里把 $x=1$，$y=-1$ 带进去得证。

式子六：$\varphi*I=Id_1$，因为：

设 $p$ 为质数，$m>0$，则：

$$ \begin{aligned} (\varphi*I)(p^m)&=\sum\limits_{i|p^m} \varphi(p^m)\\ &=\sum\limits_{i=0}^m \varphi(p^i)\\ &=p^0+\sum\limits_{i=1}^m \varphi(p^i)\\ &=p^0+\sum\limits_{i=1}^m (p^i-p^{i-1})\\ &=p^m \end{aligned} $$

因为 $n$ 可分解为 $p_1^{m_1}p_2^{m_2}\dots p_k^{m_k}$，可由积性函数的性质得证 $(\varphi*I)(n)=n=Id_1(n)$。

即 $\varphi*I=Id_1$。

式子七：$\varphi=\mu*Id_1$。

这个留作作业，答案放在文尾。

简单性质

上文的式子二、四、六就是主要性质，除此之外还有积性函数性质：

若 $f$，$g$ 为积性函数，则 $f*g$ 也为积性函数。

狄利克雷的逆元

对于每个 $f(1)\ne 0$ 的 $f$，都存在一个 $g$ 使得 $f*g=\epsilon$。

如何求 $g$？

先推一下式子：

$$ \begin{aligned} f*g&=\sum\limits_{i|n} f(i)g(\frac{n}{i})\\ &=f(1)g(n)+\sum\limits_{i|n,i\ne 1}f(i)g(\frac{n}{i})\\ &=\epsilon=[n=1] \end{aligned} $$

现在目标为定义 $g(n)$ 使得等式成立。

可以定义：$g(n)=\frac{1}{f(1)}([n=1]-\sum\limits_{i|n,i\ne 1}f(i)g(\frac{n}{i}))$。

$g$ 就是 $f$ 的逆元，也可写作 $f^{-1}$。

莫比乌斯反演

莫比乌斯反演公式

在“狄卷”的“一些函数意义”中我们直接给出了 $\mu$ 的定义与运算方式。

但其实是要推的，仅知道的条件是“定义 $I$ 的逆为 $\mu$”。

让我们来看看如何用狄卷推出莫反的式子——看看狄卷是怎么降维打击的。

如果 $g=f*I$，则

$$ f=f*I*\mu=g*\mu $$

一展开，即：

如果 $g(n)=\sum\limits_{i|n}f(i)$，则

$$ f(i)=\sum\limits_{i|n}\mu(i)g(\frac{n}{i}) $$

写得优美一点：

$$ g(n)=\sum\limits_{i|n}f(i)\Leftrightarrow f(i)=\sum\limits_{i|n}\mu(i)g(\frac{n}{i}) $$

而这个就是我们的莫反公式了！

别忘了，我们尚未知道 $\mu$ 的值，现在来讲讲怎么求。

由于 $I$ 是积性函数，所以 $\mu$ 也是积性函数。简单算数可得：

$$ \mu(p^k)=\begin{cases} 1 & k=0\\ -1 & k=1\\ 0 & k>1 \end{cases} $$

再根据积性函数，就得到了：

$$ \mu(n)=\begin{cases} 1 & n=1\\ (-1)^k & n=p_1p_2\dots p_k\\ 0 & \text{other situation} \end{cases} $$

于是华丽结束。

有没有体味到降维打击呀朋友们！

莫比乌斯函数的性质

如果不讲狄卷，这里应该是第二章，但是学过狄卷的我们可以速通以下三个性质。

  1. $\sum\limits_{i|n}\mu(i)=[n=1]$。这个用 $\mu*I=\epsilon$ 秒了。
  2. $n=\sum\limits_{i|n}\varphi(i)$。用 $\varphi*I=Id_1$ 秒了。
  3. $\sum\limits_{i|n}\frac{\mu(i)}{i} = \frac{\varphi(n)}{n}$。因为 $\varphi=\mu*Id_1$，所以展开得 $\sum\limits_{i|n} \frac{\mu(i)\cdot n}{i}=\varphi(n)\Rightarrow \sum\limits_{i|n} \frac{\mu(i)}{i}=\frac{\varphi(n)}{n}$，秒了。
  4. $\mu(n)$ 是积性函数，这个上文解释过了。

代码实现预处理 $\mu$

$\mu$ 是积性函数，线性筛带走。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void init(int x)
{
    mu[1]=1;
    for(int i=2;i<=x;i++)
    {
        if(!vis[i])
            pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*pri[j]<=x;j++)
        {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) break;
            mu[i*pri[j]]=-mu[i];
        }
    }
}

参考文献

式子七答案

$$ \begin{aligned} \varphi&=\varphi *\epsilon\\ &=\varphi*I*\mu\\ &=Id_1*\mu \end{aligned} $$

结尾

有没有感受到用狄卷理解莫反“降维打击”的快感？

由于我是自学的，有一些地方会有纰漏，欢迎指出。

没有例题是因为还没去刷，大家如果想锻炼推式子能力可以看参考文献 2。

数论
Licensed under CC BY-NC-SA 4.0