「莫比乌斯反演」学习笔记

个人赶脚这个东西非常好玩。
决定安利给朋友所以有了这篇笔记。

数论函数

在数论上，数论函数指定义域为正整数、值域为实/复数的函数。
通俗地讲，我们 OI 接触到的大部分函数都是数论函数，比如： - 元函数 ϵ(n)=[n=1] - 欧拉函数 φ(n)=n−1∑i=1[gcd(n,i)=1] - 约数个数函数 d(n)=∑i|n1 - 约数和函数 σ(n)=∑i|ni

积性函数

对于一个数论函数 f，若对于所有 gcd(i,j)=1 的 i,j，都有 f(ij)=f(i)f(j)，则称函数 f 是积性函数。

特别地，如果对于所有没有限制的 i,j 上式仍成立，则称该函数是完全积性函数。

狄利克雷卷积

记两个数论函数 f,g 的狄利克雷卷积为 f∗g。
且 (f∗g)(n)=∑d|nf(d)g(nd)。

显然狄利克雷卷积具有交换律与结合律。

莫比乌斯函数

把正整数 n 分解为质因数相乘的形式 n=m∑i=1pici，有

μ(n)={1,n=10,∃i∈[1,m],ci>1(−1)m,∀i∈[1,m],ci=1

显然莫比乌斯函数也是积性函数。

如果要求 μ(n)，分解质因数即可。

如果要求 μ(1)∼μ(n)，可以线性筛。
伪代码：

getMu(n)
    mu[1] = 1
    for i in [2,n]
        if vis[i] == 0
            prime[++cnt] = i
            mu[i] = -1
        for j in [1,cnt] and i * prime[j] <= n
            vis[i * prime[j]] = 1
            if i mod prime[j] == 0
                break
        mu[i * prime[j]] = -mu[i]

有一个比较显然的性质：∑d|nμ(d)=[n=1] 即 μ∗1=ϵ。

证明：
首先，显然 μ∗1 也是积性函数。
有 (μ∗1)(1)=1。

然后考虑一个质数 p， (μ∗1)(pk)=μ(1)+μ(p)+μ(p2)+⋯+μ(pk)=1−1+0+⋯+0=0

考虑合数 x,x>1，将它分解为质因子相乘的形式 x=m∏i=1pici。
有 (μ∗1)(x)=m∏i=1(μ∗1)(pici)=0。
证毕。

然后有莫比乌斯反演公式：
如果有数论函数 f 和 F，满足 F(n)=∑d|nf(d)，有 f(n)=∑d|nF(d)μ(nd)。

证明：
我们让 F(n)=∑d|nf(d) 这个式子等号两边都卷上 μ，即 F∗μ=f∗1∗μ。
由于狄利克雷卷积有交换与结合律，所以 f∗1∗μ=f∗ϵ=f。
所以 f=F∗μ。

这个玩意有一个更为常用的形式：若 F(n)=∑n|df(d)，那么 f(n)=∑n|dF(d)μ(dn)。

其实莫比乌斯函数是基于容斥原理的。

例题 - Zap

给定 n,m,k，求 n∑i=1m∑j=1[gcd(i,j)=k]。
多组询问。

设 f(x)=n∑i=1m∑j=1[gcd(i,j)=x],F(x)=∑x|df(d)=⌊nx⌋⌊mx⌋。
于是 f(x)=∑x|dμ(dx)⌊nd⌋⌊md⌋。
考虑把枚举的东西换成 dx，有 f(x)=∑xi≤min(n,m)μ(i)⌊nxi⌋⌊mxi⌋。

但是这样还没完，我们仍然没法直接做。
换个角度思考，n∑i=1m∑j=1[gcd(i,j)=k] 相当于 ∑ki≤n∑kj≤m[gcd(i,j)=1]。
于是原式变为 min(n,m)∑i=1μ(i)⌊⌊nk⌋i⌋⌊⌊mk⌋i⌋。

运用数论分块即可解决。