初等数论学习笔记 III：数论函数与筛法( 八 ) _生活百科

\(g(n) = \sum\limits_{d\mid n} f(d)\) 的狄利克雷前缀和形式相当常见，因此根据 \(g\) 求原函数 \(f\) 也很重要。因为 \(g = f * 1\) ，所以 \(f = g * 1 ^ {-1}\) 。
设 \(h = 1 ^ {-1}\) ，根据逆元递推式推导 \(h\) 的一般形式。先将递推式写出， \(h(n) = -\sum\limits_{d\mid n, d\neq n} h(d)\) 。
由于积性函数的逆元具有积性，所以 \(h\) 具有积性。只需观察 \(h\) 在质数幂 \(p ^ k\) 处的取值即可得到一般化的结论。

\(h(p) = -h(1) = -1\) 。
\(h(p ^ 2) = -(h(1) + h(p)) = 0\) 。
\(h(p ^ 3) = -(h(1) + h(p) + h(p ^ 2)) = 0\) 。

据此，可归纳证明 \(h(p ^ k)\) 当 \(k = 0\) 时等于 \(1\) ， \(k = 1\) 时等于 \(-1\) ， \(k \geq 2\) 时等于 \(0\) 。
考虑 \(n = \prod\limits_{i = 1} ^ m p_i ^ {c_i}\) 。根据 \(h\) 的积性，若存在 \(c_i\geq 2\) 则 \(h(n) = 0\) ，否则 \(h(n)\) 等于 \((-1) ^ m\) 。容易发现这与莫比乌斯函数的定义式相符。因此 \(1 ^ {-1} = \mu\) ，即
\[\mu * 1 = \epsilon\]验证：令 \(S(n) = \sum\limits_{d\mid n} \mu(d)\) 。考虑 \(n\) 的所有质因子 \(p_1 \sim p_m\) 。对于任意 \(k\) 个质因子的乘积 \(P\) ，它产生 \(\mu(P) = (-1) ^ k\) 的贡献。因此， \(S(n)\) 可写作 \(\sum\limits_{i = 0} ^ m (-1) ^ i\dbinom m i = (1 - 1) ^ m\) 。当 \(m = 0\) 时， \(n = 1\) ， \(S(n)\) 显然为 \(1\) 。否则 \(S(n) = 0 ^ m = 0\) 。这从另一个角度说明了 \(\mu * 1 = \epsilon\) 。
也可以从容斥系数的角度理解莫比乌斯函数。设 \(g(n) = \sum\limits_{n\mid d} f(d)\) ，即 \(g(n)\) 是 \(f\) 在所有 \(n\) 的倍数处的取值和。现在已知 \(g\) ，要求 \(f(1)\) 。则 \(f(1)\) 等于 \(f\) 在 \(1\) 的倍数处的取值和，减去在质数处的取值和，但是多减去了在两个不同质数乘积处的取值和，因此要加上这些值，但是多加上了在三个不同质数乘积处的取值和，以此类推。因此，若 \(n\) 为 \(k\) 个不同质数的乘积，则 \(f(1)\) 会受到 \(g(n)\) 系数为 \((-1) ^ k\) 的贡献，如下图，图源。

文章插图
换言之，对 \(\pmb {\mathbb N}\) 做容斥原理，得到贡献系数 \(\boldsymbol \mu\) 。
5.2 筛据定义，线性筛莫比乌斯反演是容易的。

int vis[N], cnt, pr[N], mu[N];void sieve() {mu[1] = 1;for(int i = 2; i < N; i++) {if(!vis[i]) pr[++cnt] = i, mu[i] = -1;for(int j = 1; j <= cnt && i * pr[j] < N; j++) {vis[i * pr[j]] = 1;if(i % pr[j] == 0) break; // 此时 i * pr[j] 含至少两个 pr[j] ， mu = 0mu[i * pr[j]] = -mu[i]; // mu[i * pr[j]] = mu[i] * mu[pr[j]] = -mu[i]}}}

当时间复杂度可接受时，根据 \(\mu\) 的狄利克雷卷积求逆式 \(\mathcal{O}(n\log n)\) 递推更方便。
int mu[N];void sieve() {mu[1] = 1;for(int i = 1; i < N; i++)for(int j = i + i; j < N; j += i)mu[j] -= mu[i];}5.3 莫比乌斯反演\(\mu * 1 = \epsilon\) 引出了 \(\mu\) 的关键性质：\([n = 1] = \epsilon(n) = \sum\limits_{d\mid n} \mu(d)\) 。这使得我们可以用 \(\mu\) 的和式代替形如 \([n = 1]\) 的艾佛森括号，体现出其核心 “反演” 。