莫比乌斯反演

sfmmdm · 2021-01-24 12:55:03 · 个人记录

如果对于一个函数 f(n)，对其求值较为困难，但如果存在 g(n) 的约数或倍数和是 f(n)，同时 g(n) 又比较好求，我们就可以选择用 g(n) 化简 f(n)。

常见的数论函数（积性函数）

数论函数：定义域为 \mathbb{N^*} 的函数。

积性函数：若 \gcd(x,y)=1，则 f(xy)=f(x)f(y)，那么 f(x) 是积性函数。
特别的，\forall x,y\in \mathbb{N^*}, f(xy)=f(x)f(y) 则f(x) 是完全积性函数。

以下是几个常见的积性函数：

• 元函数（单位函数）：\epsilon(n)=[n=1]。（即当且仅当 n=1 ，\epsilon(n)=1，否则 \epsilon(n)=0）。

• 幂函数：id_k(n)=n^k。（当然这里的 n \in \mathbb{N^*}）。
  特别地，id_1(n) 一般称为恒等函数，可以写成 id(n)；id_0(n) 可以称为常函数，可以写成 1(n) （这个是数字 1 而不是 l）。

显然，它们都是完全积性函数，证明直接代入即可。

• 除数函数：\sigma_k(n)=\sum_{d|n}d^k。
  特别地，\sigma_0(n) 就是约数个数函数，可以写成 d(n) 或 \tau(n)；\sigma_1(n) 就是约数和函数，可以写成 \sigma(n)。

• 欧拉函数：\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]，即 1 到 n 中与 n 互质的数的个数。

• 莫比乌斯函数： \mu(n)=\begin{cases} 1&n=1\\(-1)^k& n=\prod\limits_{i=1}^k p_i\\0 &otherwise \end{cases}

即，\mu(1)=1，若 n 的约数中有完全平方数，则 \mu(n)=0，否则，若 n 有奇数个质因子，\mu(n)=-1；若 n 有偶数个质因子，则 \mu(n)=1。

这函数也都是积性函数，除数函数的证明和下文相关，这里先证明欧拉函数和莫比乌斯函数。

我们知道（不知道也没关系） 若 n= \prod\limits_{i=1}^m p_i^{c_i}，则 \varphi(n)=n\prod\limits_{i=1}^m(1-\dfrac {1}{p_i})，如果 x,y 互质，则直接把 \varphi(x),\varphi(y),\varphi(xy) 展开即可证明。

狄利克雷卷积

对于两个数论函数 f,g，定义它们的狄利克雷卷积 (f*g)(n)= \sum_{d|n} f(d)g(\frac{n}{d})。

这个卷积有一些经典的性质，比如交换律结合律分配律等很显然，这里就不证明了。

除此之外还有一些其他性质：

1. 对于两个积性函数，它们的狄利克雷函数仍然是积性函数：

令 f*g=h 则

因为 x,y 互质，所以 x,y 的所有约数都是互质的（显然），又因为 f,g 都是积性函数，所以可以直接把 f,g 乘起来，得：

因为 x,y 互质，这样枚举 d_1,d_2 不会有 d_1d_2 重复，这和直接枚举 xy 的约数是等价的。

这样我们就证明了，若 \gcd(x,y)=1，则 h(xy)=h(x)h(y)。

2. 狄利克雷卷积的单位元是 \epsilon(n)

设任意数论函数 f，f*\epsilon(n)=\sum_{d|n}[d=1]f(\frac{n}{d})=f(n)。

几个比较常用的狄利克雷卷积的结果

• id_k*1(n)=\sum_{d|n}d^k=\sigma_k(n)

因此除数函数都是积性函数。

• \varphi*1(n)=id(n)

证明：（p 是质数）

根据 \varphi(p^k)=p^k-p^{k-1}，（特别地\varphi(p^0)=1）

中间全部抵消，得：

根据积性函数狄利克雷卷积仍是积性函数，对于任意 n \neq 1，将其质因数分解再相乘，即可证明 \varphi*1=id。

特别地，\varphi*1(1)=1 成立。

• 1*\mu(n)=\epsilon(n)

证明：仍然先证明对 p^k 成立：

明显，当且仅当 i=0 时，\mu(p^i)=1，当且仅当 i=1 时，\mu(p^i)=-1。

因此 \forall p^k,1*\mu(p^k)=0=\epsilon(p^k)，根据积性函数，可证明对于任意 n \neq 1 成立。

特别地，1*\mu(1)=1=\epsilon(1) 成立。

因此对于任意正整数 n，有1*\mu(n)=\epsilon(n)。

这个性质非常重要，因为 \epsilon 是单位元，这个性质证明了，莫比乌斯函数和常函数在狄利克雷卷积下互为逆元。

因此，f=1*g \Leftrightarrow \mu*f=g*1*\mu=g

展开就是 f(n)=\sum_{d|n}g(d) \Leftrightarrow g(n)=\sum_{d|n}f(d)\mu(\frac{n}{d})。

如果函数 g 不好求，但 f 好求，就可以先求出 f 然后通过 \mu 把 g 转换为 f 的卷积，就可以求出 g。

这样，通过莫比乌斯函数，把 f=\sum g 的形式转换为 g=\sum f 的过程就叫莫比乌斯反演。

莫比乌斯反演

进入正题，莫比乌斯反演有两条定理：

第一条已证明，现在证明第二条：

然而这条并不常用，一般只用第一条就够了。

莫比乌斯反演是怎么用的呢，让我们用几道例题看一看。

例1:

我们看到了一个中括号，因此很容易想到 \epsilon 函数，我们把 k 提出来，把式子变成：

这里的 i,j 在枚举 k 的倍数，在反演推式子时，我们一般会用直接 i,j 枚举 \frac i k,\frac j k 的结果，这是反演中第一个常见套路：对枚举变量换元。

我们发现 \gcd 是二元函数，不好化简，那么我们可以将 \epsilon 展开成 \mu * 1 的形式，即：

于是我们顺利地把 \gcd 转移到了求和条件里，让式子看起来更恐怖了。

其实并不会，d 枚举的是 \gcd 的约数，那么我们就可以找到一个等价条件，式子化成：

接着，就是反演中另一个常用的套路：交换枚举顺序，这样，我们就可以把 \mu 提前，方便化简，优先枚举 d，式子化为：

明显：

这样我们就把一个 O(n^2) 算完的式子转化成了 O(n)，如果再加上数论分块的技巧，则又可以优化到 O(n)-O(\sqrt n)。

例2

为转化成例1的形式，我们枚举 \gcd 的值，后面变成 [\gcd=1]。

反演 \epsilon 并交换枚举顺序

这时又会有一个常用的换元，我们先枚举 d,g 的乘积 T，这样 d 就会枚举 T 的约数，从而使得式子更靠近狄利克雷卷积的形式。

等等，后面那是 \mu*1，这不就是\varphi 吗，于是

然后就很好求了。

补充内容

线性筛

数论分块