Mobius - 莫比乌斯反演

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

最常用的推导就是这个：

\begin{aligned} \sum_{i = 1}^{n} \sum_{j = 1}^{m} [gcd (i, j) = 1] \\ = & \sum_{i = 1}^{n} \sum_{j = 1}^{m} ϵ (gcd (i, j)) \\ = & \sum_{i = 1}^{n} \sum_{j = 1}^{m} \sum_{d | gcd (i, j)} μ (d) \\ = & \sum_{d = 1}^{min (n, m)} μ (d) ⌊ \frac{n}{d} ⌋ ⌊ \frac{m}{d} ⌋ \end{aligned}

$\gcd$ $\epsilon$ $\mu$ 。

写成狄利克雷卷积的形式就是：

ϵ = μ * 1

不过这玩意一般没啥用。。。

整个莫比乌斯反演的结论用一般写法就是：

\begin{aligned} f (n) = \sum_{d | n} g (d) \\ ⟹ & g (n) = \sum_{d | n} μ (n) f (\frac{d}{n}) \end{aligned}

狄利克雷卷积写法的话是：

f = g * 1 ⟹ g = f * μ

$\epsilon$ $f \ast \epsilon = f$ 。

然后也存在逆元（狄利克雷逆），求法是一大坨式子，基本用不上，然后群论那一套东西这玩意似乎都符合。

然后有这么几个常用的函数：

莫比乌斯函数 $\mu(x)$ ：略了（式子太长懒得写 latex 了）。

欧拉函数 $\varphi(x)$ ：应该都知道吧。

单位函数 $\epsilon(x)$ $\epsilon(x) = \left[ x = 1 \right]$ 。

恒等函数 $\operatorname{Id}(x)$ $\operatorname{Id}(x) = x$ 。

常数函数 $1(x)$ $1(x) = 1$ 。

约数个数函数 $d(x)$ $d(x) = \sum_{i \vert x}1$ 。

约数和函数 $\sigma(x)$ $\sigma(x) = \sum_{d \vert x}d$ 。

ϵ = μ * 1

d = 1 * 1

Id * 1 = σ

μ * Id = φ

φ * 1 = Id

证明懒得写了。。。

$LHS$ $\gcd$ 分组感性理解一下，~~虽然我没完全明白~~。

然后关于归纳法的严格证明看到了一个很严谨的，戳此查看。（~~看不懂~~）

$\mu$ $1$ ，这样莫比乌斯反演也就很好证了。。。

$f \ast \epsilon = f$ $\mu \ast 1 = \epsilon$ ，所以有：

\begin{aligned} f & = g * 1 \\ f * μ & = g * 1 * μ \\ f * μ & = g * ϵ \\ f * μ & = g \end{aligned}

嗯这个是从 zpair 的 blog 里抄过来的，挺人类智慧。

φ (i j) = \frac{φ (i) φ (j) gcd (i, j)}{φ (gcd (i, j))}

φ (i) φ (j) = φ (gcd (i, j)) φ (lcm (i, j))

d (i j) = \sum_{x | i} \sum_{y | j} [gcd (x, y) = 1]

大概这样。。。

update-2022_09_23 初稿