下面的内容，只能领进门，不能直接拿去做题>_<

不过可以和进阶课或者别的什么一起看。有错误的话还请直接指出，不吝指教。

莫比乌斯反演作为一种技巧，应用于 某些式子 的化简。所以有用的还是怎么分析才得用上 $\mu(x)$之类的函数。

介绍

由于会反复用到某些概念，这里提前给出声明。

约定质数集为 $\mathbb{P}$，$b \mid a$ 表示 $a$ 能够被 $b$ 整除，也即 $a \equiv 0 \pmod b$；由模运算，本文的讨论范围只限于正整数域。

暂且不严谨地考察黎曼 $\zeta$ 函数，有

$$\zeta(s)=\sum\limits_{n=1}^{\infty}\dfrac{1}{n^s}=\dfrac{1}{1^s}+\dfrac{1}{2^s}+\dfrac{1}{3^s}\cdots$$

考虑等比数列化简过程中用过的套路——乘某个重复出现过的数然后相减。对于上式此时有

$$\begin{aligned} &\dfrac{1}{2^s}\zeta(s)=\dfrac{1}{2^s}+\dfrac{1}{4^s}+\dfrac{1}{6^s}\cdots \\ \Rightarrow &(1-\dfrac{1}{2^s})\zeta(s)= \dfrac{1}{1^s} + \dfrac{1}{3^s} + \dfrac{1}{5^s} +\cdots \\ \Rightarrow &\dfrac{1}{3^s}(1-\dfrac{1}{2^s})\zeta(s)= \dfrac{1}{3^s} + \dfrac{1}{9^s} + \dfrac{1}{15^s} +\cdots \\ \Rightarrow &(1-\dfrac{1}{3^s})(1-\dfrac{1}{2^s})\zeta(s)= \dfrac{1}{1^s} + \dfrac{1}{5^s} + \dfrac{1}{7^s} +\cdots\\ \ldots \\ \Rightarrow & \zeta(s)\prod\limits_{p \in \mathbb{P}}(1-\dfrac{1}{p^s})=\dfrac{1}{1^s}=1\\ \Rightarrow & \prod\limits_{p \in \mathbb{P}}(1-\dfrac{1}{p^s})= \dfrac{1}{\zeta(s)}. \end{aligned}$$

所以，欧拉乘积（因为上述方式是欧拉最先找到的）架通了黎曼函数与质数之间的桥。但这不是现在讨论的重点，重点是考虑将连乘式展开后会怎样。此时则有

$$\dfrac{1}{\zeta(s)}=\prod\limits_{p\\ \in \\ \mathbb{P}}(1-\dfrac{1}{p^s})=1-(\dfrac{1}{2^s} + \dfrac{1}{3^s}+\cdots)+(\dfrac{1}{6^s}+\dfrac{1}{10^s}+\cdots)-\cdots$$

可以发现，单个质数的符号是负数；某些合数:

1. 是没算到的；
2. 符号是负的；
3. 符号是正的。

而出现这三种现象的原因是

• 没有展开之前，每个质数带负号；
• 每个质数只有一个。

于是可以借此归纳出一个函数，用于表示这样的性质。而这些工作前人都已经做好了，这个函数叫莫比乌斯函数。定义如下。
$$\mu(x)=\begin{cases} (-1)^r, &x=\prod\limits_{i=1}^{r}p_i \\ 0, &\exists p \in \mathbb{P}, p^2\mid x \\ 1,&x=1 \end{cases}$$

这个时候黎曼函数的倒数可以写成 $\dfrac{1}{\zeta(s)}=\sum\limits_{i=1}^{\infty}\dfrac{\mu(n)}{n^s}$。

而由刚刚 从生成函数倒推函数定义 的过程，我们不难挖掘出莫比乌斯函数的性质。但在此之前，先回过头来考虑以另一种方式贡献到对应项的卷积——狄利克雷卷积。卷积的形式是

$$(f*g)(n)=\sum\limits_{x \mid n} f(x)g(\frac{n}{x})=\sum\limits_{xy=n}f(x)g(y)$$

等式的最右侧直观显示出了该卷积的内涵。从此起，本文称之为乘法卷积。基于元的轮换对称性，显然乘法卷积是可交换的。考察是否可结合。此时有

$$((f*g)*h)(n)=\sum\limits_{xy=n}\left(\sum\limits_{uv=y}f(u)g(v)\right)h(x)=\sum\limits_{xy=n}\sum\limits_{uv=y}f(u)g(v)h(x)=\sum\limits_{uvx=n}f(u)g(v)h(x)$$

然后发现通过交换又能证明出来了。同时还能看到，乘法卷积也是可分配的。

而当函数与“常值函数” $y(n)=1$ 做乘法卷积时，有

$$(f*1)(n)=\sum\limits_{xy=n}f(x) = \sum\limits_{x \mid n}f(x)$$

相当于 将下标是 $n$ 的所有因子 的项抽出来求和贡献到新函数 $F(n)$ 中。以卷积的记法，可以表示为

$$F=f*1$$

按此考察莫比乌斯函数，有

$$(\mu*1)(n)=\sum\limits_{xy=n}\mu(x) = \sum\limits_{x \mid n}\mu(x) = \sum\limits_{x=1}^n[x\mid n]\mu(x)$$

因算术基本定理成立，我们需要分类讨论 $n$。

• 如果 $n=1$，上式算得 $\mu(1)=1$。
• 如果 $n$ 是质数，那么上式只能展开为 $\mu(1)+\mu(n)=1-1=0$。
• 如果 $n$ 是合数：
  • 如果可以整除某个质数 $p_x$ 的平方或者更高次幂，我们考虑 $\mu(x)$ 的性质。对于数字 $x,y$ 而言，假如存在 $\gcd(x,y)\ne 1$，那么 $\mu(xy)=\mu(\gcd ^2(x,y)\cdot \text{other})=0$。所以，只要 $\exists p \in \mathbb{P},p^2|n$ 时，对于含有质数平方因子的项，莫比乌斯函数值均为 $0$。也因此，只需要考察那些不含有质数平方因子的项即可。那么讨论见下。
  • 如果不能，计算过程变成了排列组合的过程。考虑 $n$ 可由 $m$ 个质数相乘而完全表示。这时有
    $$\begin{aligned}&\mu(1)+(\mu(p_1)+\cdots+\mu(p_{m}))+\sum\mu(p_ip_j)+\cdots+\mu(p_1p_2\ldots p_{m})\\ \Rightarrow &\sum\limits_{x \mid n}\mu(x)= 1 + \dbinom{1}{m}(-1) + \dbinom{2}{m}(-1)^2+\cdots+\dbinom{m}{m}(-1)^m=(1-1)^m=0 \end{aligned}$$

由此我们证明了

$$(\mu*1)(n)=\sum\limits_{x \mid n}\mu(x)=\begin{cases}1,&n=1\\0,&n \ne 1,n\in\mathbb{N}^+\end{cases}$$

不妨把它记为 $e(n)$。因为对于这个函数，与其它函数做乘法卷积时，总有

$$(e*f)(n)=\sum\limits_{xy=n}e(x)f(y)=e(1)f(n)=f(n)$$

也就是乘法卷积卷是卷了，但是函数没有变化，这完全符合单位元的定义。

所以可以惊奇地发现，刚刚的“常值函数”与莫比乌斯函数在乘法卷积中互为逆。也因此，就有所谓的莫比乌斯反演

$$F(n)=f*1=1*f \quad \Rightarrow f(n)=F* \mu=f*1*\mu=f*e$$

而且，对于最常用的转换，要属

$$\sum\limits_{x\mid n}\mu(x)=[n=1]=[\gcd(i,j)=1]=\sum\limits_{x\mid \gcd(i,j)}\mu(x) =\sum\limits_{\substack{x \mid i \\ x\mid j}}\mu(x)$$
至于原因…

示例

以进阶课里的【SDOI2015·约数个数和】为例，题目要我们求 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(1*1)(ij)$。

为了区别于题目中的表示，以下的记号做出了变化。但含义理应是不明而自知的。

我们先来看 $(1*1)(N)$ 等于什么吧。根据卷积定义，有
$$(1*1)(N)=\sum\limits_{xy=N}1(x)1(y)=\sum\limits_{xy=N}=\sum\limits_{x\mid N}$$

也就是说，算出 $N$ 所有因数的数量。

人们常把它记为 $d(n)=(1*1)(n)$。

但不管怎么说，代入原式有

$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{xy=ij}1(x)1(y) = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x\mid ij}= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x = 1}^{ij}[x \mid ij]$$

考虑到任何一个数都能表示为 $i = p_1^{a_1}p_2^{a_2}\cdots p_{k}^{a_{k}},j = p_1^{b_1}p_2^{b_2}\cdots p_{k}^{b_{k}};\forall i \in \{o|1\leq o \leq k,o\in \mathbb{Z}\},p_i \in \mathbb{P}; a_i,b_i \geq 0$ 的形式，由此可以得到
$$ij= p_1^{a_1+b_1}p_2^{a_2+b_2}\cdots p_{k}^{a_{k}+b_{k}}$$

同时还有结论：对于某个数的因数个数，比如 $i = p_1^{a_1}p_2^{a_2}\cdots p_{k}^{a_{k}}$，那么根据排列组合的知识，可以知道 $i$ 就有 $(1+a_1)(1+a_2)\cdots(1+a_k)$ 个因数。

也因此，对于 $ij$ 而言，有 $(1+a_1+b_1)(1+a_2+b_2)\cdots(1+a_k+b_k)$ 个因数。

如果要使 $x$ 成为 $ij$ 的因数，就需要 $x$ 有或者没有 $ij$ 中所出现过的质数（最低的要求就是 $x=1$）。

由于直接枚举 $x$ ，时间复杂度不可接受，又考虑到对于所有质数 $p_u$，$i$ 贡献到 $p_u^{a_u+b_u}$ 的部分是 $p_u^{a_u}$；$j$ 贡献到 $p_u^{a_u+b_u}$ 的部分是 $p_u^{b_u}$。

所以完全可以在二重循环 $i,j$ 中枚举所有满足 $x=s\cdot t;\ \ s\mid i,t\mid j,\gcd(s,t)=1$ 的 $(s,t)$ 对与 $(i,j)$ 对应以减少重复计算。

构造的方式基于 存在条件限制 的排列组合。

$s\mid i,t\mid j,\gcd(s,t)=1$ 意思就在说，$p_u^{a_u+b_u}$ 要么由 $i$ 所持有的 $p_u^{a_u}$ 贡献到，要么由 $j$ 所持有的 $p_u^{b_u}$ 贡献到，绝不能出现 $i,j$ 的两个因数 $s,t$ 都同时贡献到 $p_u^{a_u+b_u}$ 的情况（不然不能保证两者互素）。也由此，这样就确保了对每一个计算到 $x$ 的质数 $p_u$ 都有 $(1+a_u)(1+b_u)=1+b_u+a_u+\color{red}{0} =(1+a_u+b_u)$ 种可行的取值。

至于别人是怎么找到的，我想这可能是所谓的数感吧。后面的枚举也是，一般人不能轻易想到的。倒是这种通过构造来证明的思路值得好好学学。

式子从而可以被 “化简” 为
$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x = 1}^{ij}[x \mid ij]=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{s=1}^{n}[s \mid i]\sum\limits_{t=1}^{m}[t \mid j]\left[\gcd(s,t)=1\right]=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{s \mid i}\sum\limits_{t \mid j}[\gcd(s,t)=1]$$

进一步有
$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{s \mid i}\sum\limits_{t \mid j}[\gcd(s,t)=1]= \left(\sum\limits_{i=1}^{n}\sum\limits_{s \mid i}\right) \left(\sum\limits_{j=1}^{m}\sum\limits_{t \mid j}\right)[\gcd(s,t)=1]$$

考虑单个 $\sum\limits_{i=1}^{n}\sum\limits_{s \mid i}$ 且 $n=9$，当遍历 $i$ 时，$s$ 应该取的值。

$$\begin{matrix} 1 \\ 1 &2 \\ 1 & &3 \\ 1 &2 & &4\\ 1 & & & &5 \\ 1 &2 &3 & & &6 \\ 1 & & & & & &7 \\ 1 &2 & &4 & & & &8 \\ 1 & &3 & & & & & &9 \\ \end{matrix}$$

原本是横向枚举然后累计个数，但是不难发现纵向枚举也能做到相同的功效而且还消掉了一个求和符号。只需要 $\sum\limits_{i=1}^n \lfloor \dfrac{n}{i} \rfloor$ 或者 $\sum\limits_{s=1}^n \lfloor \dfrac{n}{s} \rfloor$ 就好。

所以等式变为
$$\left(\sum\limits_{i=1}^{n}\sum\limits_{s \mid i}\right) \left(\sum\limits_{j=1}^{m}\sum\limits_{t \mid j}\right)[\gcd(s,t)=1]= \sum\limits_{s=1}^n \lfloor \dfrac{n}{s} \rfloor\sum\limits_{t=1}^m \lfloor \dfrac{m}{t} \rfloor [\gcd(s,t)=1]= \sum\limits_{s=1}^n \sum\limits_{t=1}^m \lfloor \dfrac{n}{s} \rfloor\lfloor \dfrac{m}{t} \rfloor [\gcd(s,t)=1]$$

由于 $\gcd(s,t)$ 阻碍推导，不妨换回莫比乌斯函数。

$$\sum\limits_{s=1}^n \sum\limits_{t=1}^m \lfloor \dfrac{n}{s} \rfloor\lfloor \dfrac{m}{t} \rfloor \sum\limits_{v \mid \gcd(s,t)}\mu(v)$$

然后考虑直接先枚举 $v$。由于 $v \mid \gcd(s,t)$，这表示 $v \mid s$ 且 $v \mid t$。那么再做一点变形就可以有

$$\sum\limits_{s=1}^n \sum\limits_{t=1}^m \lfloor \dfrac{n}{s} \rfloor\lfloor \dfrac{m}{t} \rfloor \sum\limits_{v \mid \gcd(s,t)}\mu(v) =\sum\limits_{v=1}^{\min(n,m)}\sum\limits_{s=1}^{n}[v \mid n]\lfloor \dfrac{n}{s} \rfloor \sum\limits_{t=1}^{m}[v \mid m] \lfloor \dfrac{m}{t} \rfloor \mu(v) =\sum\limits_{v=1}^{\min(n,m)}\sum\limits_{s=1}^{\lfloor\frac{n}{v} \rfloor} \sum\limits_{t=1}^{\lfloor\frac{m}{v}\rfloor} \lfloor \dfrac{n}{vs} \rfloor\lfloor \dfrac{m}{vt} \rfloor \mu(v) =\sum\limits_{v=1}^{\min(n,m)}\left(\sum\limits_{s=1}^{\lfloor \frac{n}{v} \rfloor} \lfloor \dfrac{n}{vs} \rfloor \right)\left( \sum\limits_{t=1}^{\lfloor\frac{m}{v}\rfloor}\lfloor \dfrac{m}{vt} \rfloor \right) \mu(v)$$

所以

$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(1*1)(ij)=\sum\limits_{v=1}^{\min(n,m)}\left(\sum\limits_{s=1}^{\lfloor \frac{n}{v} \rfloor} \lfloor \dfrac{n}{vs} \rfloor \right)\left( \sum\limits_{t=1}^{\lfloor\frac{m}{v}\rfloor}\lfloor \dfrac{m}{vt} \rfloor \right) \mu(v)$$

完全没有用到什么莫比乌斯反演。 不过是初等数论的推理和交换求和次序之类的小技巧罢了。

实现

这里只给出 $\mu(x)$ 怎么算。既然和质数有关，那就在线性筛里算 $\mu(x)$ 就好了。

void init(int n)
{
    mu[1] = 1; 
    for(int i=2;i<=n;++i)
    {
        if(!vis[i]) prime[cnt++] = i,mu[i] = -1; // 是质数就是-1

        for(int j = 0;j<cnt and prime[j] * i <= n;++j)
        {
            vis[prime[j] * i] = 1;
            if(i%prime[j]==0)break;
            mu[prime[j] * i] -= mu[i]; // 这种写法短是短，但是有点抽象。可以换成下面的
    /*
            vis[prime[j] * i] = 1;
            mu[prime[j] * i] = mu[i] * mu[prime[j]]; // 按定义乘起来
            if(i%prime[j]==0){mu[prime[j] * i] = 0; break;} // 平方项的赋0

    */
        }
    }
    // 后面一般是前缀和之类的
}

后记

数论也是个令人头大的东西……而且收益也不太高（？我还是暂时搁搁笔吧。

参考资料

• 狄利克雷卷积和莫比乌斯反演
• 读懂黎曼猜想（1）——莫比乌斯反演