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

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]\) 的艾佛森括号，体现出其核心 “反演” 。

用和式代替判断式往往重要但不直观，所以初学者难以理解 OI 常见反演技巧。例如，对于奇质数 \(p\) 有 \(\sum\limits_{x = 1} ^ {p - 1} [x ^ 2 = a] = \left(\dfrac a p\right) + 1 = (a ^ {\frac{p - 1} 2} \bmod p) + 1\)；单位根反演 \([n\mid a] = \dfrac 1 n\sum\limits_{i = 0} ^ {n - 1} \omega_n ^ {ia}\) 。从判断式到和式的过程形成套路，深入了解其背后的逻辑有助于读者掌握并熟练运用这种套路。

莫比乌斯反演的结论：

若 \(g(n) = \sum\limits_{d\mid n} f(d)\)，则 \(f(n) = \sum\limits_{d\mid n} \mu(d) f\left(\dfrac n d\right)\) 。即若 \(g = f * 1\)，则 \(f = g * \mu\) 。
若 \(g(n) = \sum\limits_{n\mid d} f(d)\)，则 \(f(n) = \sum\limits_{n\mid d} \mu\left(\dfrac d n\right) g(d)\) 。这其实就是上一节末尾提到的 \(\mu\) 作为容斥系数。验证：\(\sum\limits_{n\mid d} \mu\left(\dfrac d n\right) \sum\limits_{d\mid k} f(k) = \sum\limits_{n\mid k} f(k) \sum\limits_{d\mid \frac k n} \mu(d) = f(n)\) 。
因为 \(\varphi * 1 = \mathrm{id}\)，所以 \(\mathrm{id} * \mu = \varphi\)，即 \(\sum\limits_{d \mid n} \dfrac n d \mu(d) = \varphi(n)\) 。变式为 \(\sum\limits_{d\mid n} \dfrac{\mu(d)} d = \dfrac {\varphi(n)} n\) 。

莫比乌斯反演的常见应用：
\[[\gcd(i, j) = 1] = \sum\limits_{d\mid \gcd(i, j)} \mu(d)\]别看它只是将 \(\gcd(i, j)\) 带入 \(n\) ，但这一步将 “\(i, j\) 互质” 这个条件转化为枚举 \(\gcd(i, j)\) 的约数 \(d\) ，然后对 \(\mu(d)\) 求和。在 \(i, j\) 同样需要枚举的时候，可以先枚举 \(d\) 并计算合法的 \((i, j)\) 对数，这样 \(i, j\) 合法当且仅当 \(d\mid i\) 且 \(d\mid j\)，就把 \(i, j\) 独立开了。
5.4 常见技巧\[\begin{aligned}\sum\limits_{i = 1} ^ n \sum\limits_{j = 1} ^ m [\gcd(i, j) = 1] & = \sum\limits_{i = 1} ^ n \sum\limits_{j = 1} ^ m \sum\limits_{d\mid \gcd(i, j)} \mu(d) \\& = \sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \sum\limits_{i = 1} ^ n \sum\limits_{j = 1} ^ m [d\mid i\land d\mid j] \\& = \sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \left\lfloor \dfrac n d \right\rfloor \left\lfloor \dfrac m d \right\rfloor \\\end{aligned}\]相当于对 “最大公约数为 \(d\) 的倍数” 中的 \(d\) 做容斥：加上最大约数为 \(1\) 的倍数的对数，减去最大公约数为 \(p_i\) 的倍数的对数，加上最大公约数为 \(p_ip_j(i \neq j)\) 的倍数的对数，以此类推，得到每个 \(d\) 的贡献系数即莫比乌斯函数。
\[d(ij) = \sum\limits_{x \mid i}\sum\limits_{y\mid j} [x\perp y]\]考虑单个质因子 \(p\)，再用中国剩余定理合并。设 \(a = v_p(i)\) 即 \(i\) 含质因子 \(p\) 的数量，\(b = v_p(j)\)，则 \(v_p(ij) = a + b\) 。对于 \(ij\) 的约数 \(d\)，若 \(v_p(d) \leq a\)，则令其对应 \(v_p(x) = v_p(d)\) ， \(v_p(y) = 0\)；若 \(v_p(d) > a\) ，则令其对应 \(v_p(x) = 0\)，\(v_p(y) = v_p(d) - a\) 。容易发现互质对 \((x, y)\) 和 \(d\) 之间形成双射，因此对 \(d\) 计数相当于对 \([x\perp y]\) 计数。例 XII.
5.5 例题让我们在例题中感受莫比乌斯反演的广泛应用。除特殊说明，以下所有分式均向下取整。
I. P2522 [HAOI2011] Problem b二维差分将和式下界化为 \(1\)，然后推式子：
\[\sum_{i = 1} ^ n \sum_{j = 1} ^ m [\gcd(i, j) = k]\]只有 \(k\) 的倍数有用，将和式缩放 \(k\) 倍，得
\[\sum_{i = 1} ^ {\frac n k} \sum_{j = 1} ^ {\frac m k} [\gcd(i, j) = 1]\]莫比乌斯反演，得
\[\sum_{i = 1} ^ {\frac n k} \sum_{j = 1} ^ {\frac m k} \sum_{d\mid \gcd(i, j)} \mu(d)\]枚举约数 \(d\) ，记 \(c = \min\left(\dfrac n k, \dfrac m k\right)\)，
\[\sum_{d = 1} ^ c \mu(d) \sum_{i = 1} ^ {\frac n k} [d\mid i] \sum_{j = 1} ^ {\frac m k} [d\mid j]\]由于 \(1\sim x\) 中 \(y\) 的倍数有 \(\dfrac x y\) 个，故原式简化为
\[\sum_{d = 1} ^ c \mu(d) \dfrac n {kd} \dfrac m {kd}\]整除分块即可，时间复杂度 \(\mathcal{O}(n + T\sqrt n)\)，注意非必要不开 long long 。代码。
II. SP5971 LCMSUM - LCM Sum\[\begin{aligned}\mathrm{answer} & = \sum\limits_{i = 1} ^ n \operatorname{lcm}(i, n) \\& = n \sum\limits_{i = 1} ^ n \frac{i}{\gcd(i, n)} \\& = n \sum\limits_{d\mid n} \sum\limits_{i = 1} ^ n \frac{i}{d} [\gcd(i, n) = d] \\& = n \sum\limits_{d\mid n} \sum\limits_{i = 1} ^ {\frac n d} i \left[\gcd\left(i, \frac n d\right) = 1\right]\end{aligned}\]设 \(F(n)\) 表示 \(n\) 以内所有与 \(n\) 互质的数的和。当 \(n \geq 2\) 时，因为若 \(x\perp n\) 则 \(n - x\perp n\)，所以与 \(n\) 互质的数成对出现且和为 \(n\) 。也就是说，每个与 \(n\) 互质的数对 \(F(n)\) 的平均贡献是 \(\dfrac n 2\) 。因此 \(F(n) = \dfrac{n\varphi(n)} 2\) 。