关于莫比乌斯反演的一些思考
Enoch_xm
·
·
算法·理论
本来今年初就该写的，咕到了现在。
推荐阅读：
-
OI-Note Chapter4.1 整除与同余 - command-block
-
OI-Note Chapter4.2 数论函数与求和 - command-block
-
数论函数与筛法 (Part 1) - Alex_Wei
-
算法学习笔记 (4)：莫比乌斯反演 - GhostLX
-
莫比乌斯反演总结 - Dexterha
-
狄利克雷卷积上的特殊情况优于 nlogn 的做法 - pp-orange
引入
作者看了很多莫比乌斯反演入门的博客，总体来说讲的方法都是将 [\gcd(i, j) = 1] 拆成：
[i \perp j] = [\gcd(i, j) = 1] = \sum_{d | \gcd(i, j)} \mu(d) = \sum_{d} [d \mid i][d \mid j] \mu(d)
然后重新排列求和号，尝试一种好计算的求和顺序以简化枚举量，降低复杂度，这通常需要经验与运气（参见 P7486 题解区，你能看到很恐怖的推式子）。但笔者认为莫反问题的做法是极其机械的，难点完全不在推式子（暴论：甚至完全没有推式子），但很多文章没有体现出莫反机械的一面。
本文章旨在给出以下问题的通用求法：
\sum_{x_1 = 1}^{n_1} \sum_{x_2 = 1}^{n_2} \cdots \sum_{x_m = 1}^{n_m} f(\gcd(x_1, x_2, \cdots, x_m)) \prod_{i = 1}^m F_i(x_i)
虽然本文完全是拾人牙慧，但还是希望能给大家一些启发。
Part 1.
先考虑弱化版，F_i(\cdot) = 1，且 f 是积性函数，变为莫比乌斯反演经典问题：
\sum_{x_1 = 1}^{n_1} \sum_{x_2 = 1}^{n_2} \cdots \sum_{x_m = 1}^{n_m} f(\gcd(x_1, x_2, \cdots, x_m))
令 g = (f \ast \mu)，可以得到 (\mathbf{1} \ast g)(n) = \sum_{d | n} g(d) = f(n)。我们可以依据 g 化简
\begin{align*}
&\sum_{x_1 = 1}^{n_1} \sum_{x_2 = 1}^{n_2} \cdots \sum_{x_m = 1}^{n_m} f(\gcd(x_1, x_2, \cdots, x_m))\\
=& \sum_{x_1 = 1}^{n_1} \sum_{x_2 = 1}^{n_2} \cdots \sum_{x_m = 1}^{n_m} (\mathbf{1} \ast g)(\gcd(x_1, x_2, \cdots, x_m))\\
=& \sum_{x_1 = 1}^{n_1} \sum_{x_2 = 1}^{n_2} \cdots \sum_{x_m = 1}^{n_m} \sum_{d | \gcd(x_1, x_2, \cdots, x_m)} g(d)\\
=& \sum_{d = 1}^{\min n_i} \sum_{x_1 = 1}^{\lfloor\frac{n_1}{d}\rfloor} \sum_{x_2 = 1}^{\lfloor\frac{n_2}{d}\rfloor} \cdots \sum_{x_m = 1}^{\lfloor\frac{n_m}{d}\rfloor} g(d)\\
=& \sum_{d = 1}^{\min n_i} g(d) \prod_{i = 1}^{m} \left\lfloor \frac{n_i}{d} \right\rfloor
\end{align*}
由于 f, \mu 均积性，且积性函数对 Dirichlet 卷积封闭，因此 g = f \ast \mu 积性。首先 g(1) = 1，对于质数 p，有 g(p) = \mu(1)f(p) + \mu(p)f(1) = f(p) - f(1)；对于 p^k 推出
\begin{align*}
g(p^k) &= \sum_{s = 0}^k f(p^s) \mu(p^{k - s})\\
&= \mu(p^0)f(p^k) + \mu(p^1)f(p^{k - 1})\\
&= f(p^k) - f(p^{k - 1})
\end{align*}
对 g = f \ast \mu 做线性筛，\prod 部分整除分块，可以做到 O(N) - O({\sum \sqrt {n_i}})，其中 N 是询问 n_i 的上界。
观点：莫比乌斯反演本质是将 f 看作 1 \ast g，然后如果括号里的东西是 \gcd 状物，\sum_{d \mid \gcd(\cdots)} 就可以变成枚举 \gcd 里面 (\cdots) 的因数，以此简化运算。
Part 2.
莫比乌斯反演通用形式：
\sum_{x_1 = 1}^{n_1} \sum_{x_2 = 1}^{n_2} \cdots \sum_{x_m = 1}^{n_m} f(\gcd(x_1, x_2, \cdots, x_m)) \prod_{i = 1}^m F_i(x_i)
记：
G_i(u) = \sum_{\substack{1 \le d \le n_i \\ u \mid d}} F_i(d)
易推出
\begin{aligned}
&\sum_{x_1 = 1}^{n_1}
\sum_{x_2 = 1}^{n_2}
\cdots
\sum_{x_m = 1}^{n_m}
f(\gcd(x_1, x_2, \cdots, x_m))
\prod_{i = 1}^m F_i(x_i)\\
={}&
\sum_{x_1 = 1}^{n_1}
\sum_{x_2 = 1}^{n_2}
\cdots
\sum_{x_m = 1}^{n_m}
\left(
\sum_{d \mid \gcd(x_1, x_2, \cdots, x_m)}
(f \ast \mu)(d)
\right)
\prod_{i = 1}^m F_i(x_i)\\
={}&
\sum_{d = 1}^{\min n_i}
(f \ast \mu)(d)
\prod_{i = 1}^m
\left(
\sum_{\substack{1 \le x_i \le n_i\\ d \mid x_i}}
F_i(x_i)
\right)\\
={}&
\sum_{d = 1}^{\min n_i}
(f \ast \mu)(d)
\prod_{i = 1}^m G_i(d)
\end{aligned}
具体做法是直接计算 f \ast \mu，G_i 在其取值范围内的值，可以参考该博客。如果 f 和 F_i 是一般数论函数，能做到 O(\sum n_i \log \log n_i) 处理一次询问。如果 f 是积性函数，F_i 是完全积性函数则可以去掉 \log。
P7486 「Stoi2031」彩虹 - 线性做法
接下来尝试利用上面的观点 5 min 切掉这道题，并不需要推一坨式子，应该能吊打形如 \sum [d = \gcd(i, j)] 的一类推导。
套路地将 4-side 询问分解为 2-side 询问：
\prod_{i = 1}^n \prod_{j = 1}^m \operatorname{lcm}(i, j)^{\operatorname{lcm}(i, j)}
考虑将原式取 \log 转化为更常见的求和形式：
\begin{align*}
&\sum_{i = 1}^n \sum_{j = 1}^m \operatorname{lcm}(i, j) \log({\operatorname{lcm}(i, j)})\\
=& \sum_{i = 1}^n \sum_{j = 1}^m ij\frac{1}{\gcd(i, j)} \left(\log i + \log j - \log (\gcd(i, j))\right)\\
\end{align*}
其中分为两种求和（ij \log i 和 ij \log j 是对称的，不重复讨论）：
\sum_{i = 1}^n \sum_{j = 1}^m ij \log i \frac{1}{\gcd(i, j)}
\sum_{i = 1}^n \sum_{j = 1}^m ij\frac{\log (\gcd(i, j))}{\gcd(i, j)}
这里只讨论第一种求和，第二种求和可以用完全一致的方法推导。记 f(u) = \frac{1}{u}，F_1(u) = u，F_2(u) = u \log u，问题已经转化成 Part 2 的标准形式。
列出我们要求点值的函数 G_i：
G_1(d) = \sum_{d | u, u \le n} u
\begin{align*}
G_2(d) = \sum_{d | u, u \le m} u \log u
\end{align*}
:::info[Trick]{open}
设 $f$ 是积性函数，$g$ 是和性函数，定义 $h(n) = f(n)g(n)
\begin{align*}
h(n) &= f(n)g(n) = \left(\prod f({p_i}^{a_i})\right)\left(\sum g({p_i}^{a_i})\right)\\
&= \left[x^1\right] \prod \Big(f({p_i}^{a_i}) + f({p_i}^{a_i})g({p_i}^{a_i})x\Big)
\end{align*}
我们定义积性函数 H(p^k) = f(p^k) + f(p^k)g(p^k)x，则有 H(n) = H\big(\prod {{p_i}^{a_i}}\big) = \prod \Big(f({p_i}^{a_i}) + f({p_i}^{a_i})g({p_i}^{a_i})x\Big) = \prod H({p_i}^{a_i})，这样的好处是 h(n) = \left[x^1\right]H(n)，维护 H(n) \bmod x^2 的结果即可得到 f, h 两个函数。
| 观点：当一个数论函数本身不具有积性，可以尝试扩张函数的值域，将这部分信息编码到额外的形式变量中，从而把原函数嵌入到一个取值于更大代数结构的积性函数中。具体到这个 trick，是通过引入占位符 x 使积性点乘和性转化为积性。 |
完全性并不随着这个变换丢失，由于 i 和 \log i 都是完全积性 / 和性的，F_2 可以转变为完全积性函数。
坑：f = \frac{1}{\mathrm{id}}，这里要求逆元，但是在 \bmod P - 1 下不一定存在逆元，要是不嫌麻烦可以拆模数大力 CRT。存在更巧妙的办法，这里需要将 G_1 推出通项消掉逆元，G_1(d) = d\frac{\lfloor n / d\rfloor(1 + \lfloor n / d\rfloor)}{2}，而 (f \ast \mu)(d) = \sum_{u \mid d} \mu(u) \frac{u}{d}，这样 (f \ast \mu)(d)G_1(d) 就一个逆元都没有了，第二类求和也可以这样处理。
习题
题单内的题目基本都可以套用 Part 2 做法，有些题的难点在于题意转化。
https://www.luogu.com.cn/training/1088431