这篇文章上次修改于 488 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

算法学习笔记(4): 莫比乌斯反演前置知识

数论函数

定义在所有正整数上的函数被称为算数函数（数论函数）

积性函数

当函数f属于数论函数，且对于任意互质的正整数p，q 有f(pq) = f(p) * f(q)可称为积性函数

特别的当对于任意两个正整数p,q依旧满足上式，则可称为完全积性函数

常见积性函数

单位函数 id(n) = n
幂函数 Ik = n ^ k
常数函数 l(x) = k
因数和函数 d(x) = σ(x)
元函数 ε(x) = [1/n]
欧拉函数 φ(n)

欧拉函数定义：小于n与n互质的数的个数

性质

积性函数的和函数也是积性函数
h(x) = f(x ^ p) 和h(x) = f(x) ^ p 当f为积性函数，h也为积性函数、
设t = Π(pi^ai) (pi 为质数) 若F(x)为积性函数，F(t) = Π f(pi^ai) 的积。若F(x)为完全积性函数，F(t) = Π f(pi)^ai

整除分块（数论分块）

问题：求解当i取[1, n]时，[n/i] 的和。

[n/i] 即高斯函数，值为不超过n/i的最大整数

直接计算将会消耗O(n). 不利于求解，如果将高斯函数的值写出，观察规律就可发现，会有多项的值相同，如果想要减少复杂率就可以从这里下手。

进行举例当n为15可得数列

15, 7, 5, 3, 3, 2, 2, 1, 1, 1

易得数列必定递减，且存在值相同的区间，对于值相同的区间，如上述数列的2，2。其下标分别为 6， 7

15 / 6 = 2 和 15 / 7 = 2。对于相同区间，区间内值都为V。有n / x = v, x为数列中的下标，求得x的最大值和最小值即可计算出值相同区间的元素个数，便可快速求解。复杂度为根号级别

using i64 = long long
i64 solve(i64 n){
    i64 left, right, ans = 0;
    for(left = 1; left <= n; left = right + 1){
        right = n / (n / left);
        ans += (right - left + 1) * (n / left);
    }
    return ans;
}

狄利克雷卷积

是对两个函数的运算，两个函数运算后得到一个新的函数对于函数f和g，其狄利克雷卷积为 f * g

(f * g)(n) = ∑ f(a)g(b) [ab = n]

为所有满足ab = n情况下f(a)g(b)值之和

性质

满足交换律结合律分配率
对于元函数ε有 f * ε = f
两个积性函数的狄利克雷卷积仍然是积性函数
f = g 的充分条件 f * h = g * h
当 f * g = ε ，f和g互为逆元，积性函数的逆元仍是积性函数

莫比乌斯函数

定义

当n具有平方因子（除了1个）时，μ(n)等于0。
当n是一个平方数时，μ(n)等于0。
当n是一个质数时，μ(n)等于-1。
当n是一个有奇数个不同质因子的正整数时，μ(n)等于1。
当n是一个有偶数个不同质因子的正整数时，μ(n)等于-1。

例如
μ(330) = μ(2 * 3 * 5 * 11) = (-1)^4 = 1
μ(660) = μ(2 * 2 * 3 * 5 * 11) = 0

性质

莫比乌斯函数是积性函数

对于F(n) = ∑ μ(d) [n % d == 0]

F(n)在n等于1时值为1，在n大于1时值为0.

即 F(n) = ε(n)，F为莫比乌斯函数的和函数

证明：

对于n > 1 时，根据积性函数的定义，有F(n) = F(p1^a1)F(p2^a2)…F(p t^at)

其为质因数分解。

F(p^k) = μ(1) + μ(p) + μ(p^2) + … + μ(p^k) = μ(1) + μ(p) = 1 + -1 = 0

故F(n) 在n > 1 时只能为0

莫比乌斯反演

定义

莫比乌斯反演就是利用了莫比乌斯函数的值

对于类似莫比乌斯的和函数的相加我们有

F(1) = f(1)
F(2) = f(1) + f(2)
F(3) = f(1) + f(3)
F(4) = f(1) + f(2) + f(4)
F(5) = f(1) + f(5)
F(6) = f(1) + f(2) + f(3)
F(7) = f(1) + f(7)
F(8) = f(1) + f(2) + f(4) + f(8)

由上我们可得

f(1) = F(1)
f(2) = F(2) - F(1)
f(3) = F(3) - F(1)
f(4) = F(4) - F(2)
f(5) = F(5) - F(1)
f(6) = F(6) - F(3) - F(2) + F(1)
f(7) = F(7) - F(1)
f(8) = F(8) - F(4)

对此我们可得

f(n) = ∑ μ(d)F(n/d) [n % d == 0]

这也就是莫比乌斯反演公式。

性质

如果F是积性函数，则f也是。

对于莫比乌斯反演，f不一定要是积性函数

Mai Icy