2026.2.14 闲话：数论中的简单容斥

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\) 进制子集，而此时发现，其实这步容斥只需要二进制子集就行了。

所以自然就定义出了莫比乌斯函数。