2026.2.14 闲话：数论中的简单容斥
一些十分基础的东西，这些东西对于各位数论巨佬可能太简单了，不过还是比较有趣的。
多元 \(\operatorname{lcm}\)
首先先直接放一个式子：
\[\operatorname{lcm}(a, b) = \frac{ab}{\gcd(a, b)}
\]
这个式子肯定是显然的，我们可以有各种理解方式，比如直接理解。
再放一个。
\[\operatorname{lcm}(a, b, c) = \frac{abc\gcd(a, b, c)}{\gcd(a, b)\gcd(a, c)\gcd(b, c)}
\]
这个似乎直接理解就不方便了，暴力拆式子也不方便。
所以现在我们不妨设 \(a = p^x, b = p^y, c = p^z\)。
那么此时 \(\operatorname{lcm}(a, b, c) = p^{\operatorname{max}(a, b, c)}\)。
那么由于 \(\operatorname{min-max}\) 容斥可得：
\[\operatorname{max}(a, b, c) = a + b + c - \operatorname{min}(a, b) - \operatorname{min}(a, c) - \operatorname{min}(b, c) + \operatorname{min}(a, b, c)
\]
而由于 \(\gcd(p^x, p^y) = p^{\operatorname{min}(x, y)}\) 可以得到上式。
此时把 \(a, b, c\) 变成正常的数按位考虑其实就相同了，得到：
\[\operatorname{lcm}(a, b, c) = \frac{abc\gcd(a, b, c)}{\gcd(a, b)\gcd(a, c)\gcd(b, c)}
\]
再来个练手的：
\[\gcd(ab, bc, ac) = \frac{\gcd(a, b)\gcd(b, c)\gcd(a, c)}{\gcd(a, b, c)}
\]
不妨设 \(a = p^x, b = p^y, c = p^z\) 并且 \(x \le y \le z\)。
\[min(x + y, y + z, x + z) = x + y
\]
此时发现 \(x + y\) 就是三者之中最小和次小值相加。
所以就是 \(x + y + z - \max(x, y, z)\)。
延用上面的式子得到：\(x + y + z - \operatorname{max}(x, y, z) = \operatorname{min}(x, y) + \operatorname{min}(x, z) + \operatorname{min}(y, z) - \operatorname{min}(x, y, z)\)
得到：
\[\gcd(ab, bc, ac) = \frac{\gcd(a, b)\gcd(b, c)\gcd(a, c)}{\gcd(a, b, c)}
\]
莫比乌斯函数
这个就比较典了，就不多提了。
考虑一个狄利克雷卷积，其实就是去枚举 \(k\) 进制子集，而此时发现，其实这步容斥只需要二进制子集就行了。
所以自然就定义出了莫比乌斯函数。