莫比乌斯反演入门

· · 个人记录

狄利克雷卷积

定义:(f*g)(n)=\sum_{d|n}f(d)g(n/d)

很显然满足交换律和结合律。

积性函数

为积性函数的有:

$\epsilon (n)$ (或者$e(n)$ ),当且仅当 $n=1$ 时，其值为 $1$,否则为 $0$,其满足($e*f=f$)(因此为狄利克雷卷积的单位元) $id(n)=n$ 为单位函数。 以上为完全积性函数。 ##### 完全积性函数:对于任意整数 $a$ 和 $b$ 满足 $f(ab)=f(a)f(b)

以及：

$\mu (n)$ ,莫比乌斯函数，接下来我们重点讲，暂且不介绍。 ###### 积性函数:对于两个整数 $a,b$ ，满足 $(a,b)=1$ ，则 $f(ab)=f(a)f(b)

虽然没有完全积性函数优美，但是这很好吧，这可以吧。(

然后研究一下这个积性函数的性质。

这个易证了，f(1)=f(1)f(1)

这个稍微难一点。

证明:

定义两个积性函数 f,g ,其卷积为 G=f*g.

任取两个互质的数 a,b

G(a)G(b) =\sum_{d|a}f(d)g(b/d)*\sum_{t|b}f(t)g(b/t) =\sum_{d|a}\sum_{t|b}f(d)g(a/d)f(t)g(b/t) =\sum_{dt|ab}f(dt)g(ab/dt) =G(ab) Q.E.D.

归纳证明，就不证明了

莫比乌斯函数

引入

对于两个函数 f,F,满足 F(n)=\sum_{d|n}(1*f(d) )

等价于 F=\Iota *f,然后有 f=\Iota^{-1}*F

我们把 \Iota^{-1} 称为 \mu 莫比乌斯函数。

也就有 f=\mu *F

定义:

然后有个性质：

从定义出发易证。互逆的两个函数卷起来是单位元。

由 \varphi *1=id，且 \mu *1=e

得 \varphi * 1 *\mu=id*\mu 即 \varphi=\mu *id

然后证一下 \varphi *1=id

想了解可以参考 OI wiki

莫比乌斯反演

进入正题。

由 \mu *1=e 得 \sum_{d|n}\mu(d)=[n=1]

因为 [n|m][n/m=1]=[n=m]

所以有 [n|m]\sum_{d|(n/m)}\mu(d)=[n=m] (因为只有当n=1的时候这个玩意才满足)

可以这么转换。

因为 \sum_{d|(i,j)}\mu (d)=e(gcd(i,j) ),易证

然后你肯定是要会算莫比乌斯函数的，开筛！

这个我们之前的博客中有，于是不多说了。筛

变换形式

本质还是

F=1*f \Leftrightarrow f=F*I^{-1} \Leftrightarrow f=F*\mu

数论分块

用来计算形如 \sum_{i=1}^{n}f(i)g(\lfloor \frac{n}{i} \rfloor) 的和式。

我们再单独来讲这个 数论分块

我们推个式子：

ans=\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=1] =\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|(i,j)}\mu(d) =\sum_{d=1}^{min\{n,m\}}\mu(d)\sum_{d|i}^{n}\sum_{d|j}^{m}1 =\sum_{d=1}^{min\{n,m\}}\mu(d)\lfloor n/d \rfloor \lfloor m/d \rfloor

这个式子我们可以 O(n) 的算。

接下来我们用数论分块处理，达到 O(\sqrt{n})

总之莫反的题就是分为反演和分块，学懂了还是挺套路的。