积性函数

定义

若函数 f(n) 满足对于任意 a ⊥ b，有 f(ab) = f(a) ⋅ f(b)，则称 f 为积性函数。

若对于任意 a, b，均有 f(ab) = f(a) ⋅ f(b)，则称 f 为完全积性函数。

常见积性函数

  • 恒等函数 I(n) = 1。
  • 单位函数 ϵ(n) = [n = 1]。
  • 欧拉函数 。
  • 约数个数 d(n) = ∑i ∣ n1。
  • 约数和 σ(n) = ∑i ∣ ni。

性质

若 f 为积性函数，n = ∏piαi，则 f(n) = ∏f(piαi)。

证明

对不同质因子的个数使用数学归纳法。

当 k = 1 时，显然成立。

假设 k = m 时成立，当 k = m + 1 时，设 ，pm + 1αm + 1，显然 n′ ⊥ pm + 1αm + 1，那么 证毕。

由此可知，只需求出 f(pk) 即可求出任意 f(n)。

莫比乌斯函数

定义

莫比乌斯函数 μ(n) 定义如下： 即无平方因子否则（即有平方因子，存在）

性质

∑d ∣ nμ(d) = [n = 1]

即 ∑d ∣ nμ(d) = ϵ(n)

证明

当 n = 1 时，∑d ∣ 1μ(d) = μ(1) = 1，成立。

当 n ≠ 1 时，设 ，令 。

由于 μ(d) = 0 当且仅当 d 含有平方因子，所以只有 d ∣ n′ 时 μ(d) ≠ 0。

考虑从 k 个质因子中选 i 个组成 d，有 种选法，且 μ(d) = (−1)i，故 由二项式定理可知 证毕。

线性筛求莫比乌斯函数

由于 μ(n) 为积性函数，可以线性筛求出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
constexpr int N = 1e7 + 10;
int mu[N];
std::vector<int> primes;
bool vis[N];

void get_mu(int n) {
  mu[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) {
      primes.push_back(i);
      mu[i] = -1; // 质数的莫比乌斯值为 -1
    }
    for (auto p : primes) {
      if (i * p > n) break;
      vis[i * p] = true;
      if (i % p == 0) {
        mu[i * p] = 0; // p^2 | i*p，有平方因子
        break;
      }
      mu[i * p] = -mu[i]; // 积性函数，mu[i*p] = mu[i] * mu[p] = mu[i] * (-1)
    }
  }
}

狄利克雷卷积

定义

对于两个数论函数 f, g，它们的狄利克雷卷积为

性质

  • 交换律：f * g = g * f。
  • 结合律：(f * g) * h = f * (g * h)。
  • 分配律：f * (g + h) = f * g + f * h。
  • 单位元：f * ϵ = f。
证明单位元

因为 当且仅当 即 d = n。

常见卷积关系

其中 id(n) = n。

证明 φ * I = id

即 ∑d ∣ nφ(d) = n。

构造集合 S = {1, 2, …, n}，将 S 中的元素按照 gcd (k, n) 分类。

对于每个 d ∣ n，满足 gcd (k, n) = d 的 k 的个数即为满足 的 的个数，即 。

故 。

证毕。

证明 μ * id = φ

已知 φ * I = id，两边同时卷 μ： φ * I * μ = id * μ 又因为 I * μ = ϵ，所以 φ * ϵ = id * μ 即 φ = id * μ，也即 。

证毕。

莫比乌斯反演

定理（约数形式）

若 f(n) = ∑d ∣ ng(d) 则

证明

已知 f = g * I，两边同卷 μ： f * μ = g * I * μ = g * ϵ = g 展开即得 。

证毕。

定理（倍数形式）

若 f(n) = ∑n ∣ dg(d) 则

证明类似，此处从略。

例题

Q1

求

将 [gcd (i, j) = 1] 替换为 ∑d ∣ gcd (i, j)μ(d)： 预处理 μ 的前缀和后可以数论分块在 时间内求解。

Q2

求

设 ，则答案为 。

令 g(d) = ∑d ∣ kf(k)，即 。

由莫比乌斯反演： 代入答案： 预处理 φ 的前缀和后可以数论分块在 时间内求解。