莫比乌斯反演

莫比乌斯反演是数论中的重要内容。对于一些函数 $f(n)$ , 如果很难直接求出它的值，而容易求出其倍数和或约数和 $g(n)$ ，那么可以通过莫比乌斯反演简化运算，求得 $f(n)$ 的值。

前置芝士

数论分块， $Dirichlet$ 卷积

莫比乌斯函数

关于莫比乌斯函数的补充结论

反演结论： $\displaystyle\left[ \gcd(i, j) = 1\right] = \sum_{d \mid \gcd(i, j)} \mu(d)$

直接推导：如果看懂了上一个结论，这个结论稍加思考便可以推出：如果 $\gcd(i, j) = 1$ 的话，那么代表着我们按上个结论中枚举的那个 $n$ 是 $1$， 也就是式子的值是 $1$ 反之，有一个与 $\left[ \gcd(i,j) = 1\right]$ 相同的值： $0$

利用 $\varepsilon$ 函数 ：根据上一结论， $\left[ \gcd(i, j) = 1\right] = \varepsilon(\gcd(i, j))$ ，将 $ \varepsilon $ 展开即可。

线性筛

mu[1] = 1;
for (int i = 2; i <= N; i++)
{
	if (!flag[i]) prime[++tot] = i, mu[i] = -1;
	for (int j = 1; j <= tot && i * prime[j] <= N; j++)
	{
		flag[i * prime[j]] = 1;
		if (i % prime[j] == 0) break;
		mu[i * prime[j]] = -mu[i];
	}
}

拓展

$\varphi * 1 = \operatorname{id}$

证明：

将 $n$ 分解质因数： $\displaystyle n = \prod_{i =1 }^k p_i^{c_i}$

首先，因为 $\varphi$ 是积性函数，故只要证明当 $n' = p^c$ 时 $\displaystyle \varphi * 1 = \sum_{d \mid n'}\varphi(\dfrac{n'}{d}) = \operatorname{id}$ 成立即可。

因为 $p$ 是质数， 于是 $d = p^0, p^1, p^2, \cdots, p^c$

易知如下过程：

$\begin{aligned} \varphi \ast 1 &= \sum_{d\mid n}\varphi(\frac{n}{d})\\ &= \sum_{i = 0} ^ c\varphi(p^i)\\&= 1 + p^0\cdot(p - 1) + p ^ 1\cdot(p - 1) + \cdots + p ^ {c - 1}\cdot(p - 1)\\&= p ^ c\\&= \operatorname{id}\\ \end{aligned}$

该式子两侧同时卷 $\mu$ 可得 $\displaystyle \varphi (n) = \sum_{d\mid n}d \cdot \mu(\frac{n}{d})$

QED.

莫比乌斯变换

设 $f(n), g(n)$ 为两个数论函数。

形式一：如果有 $ f(n) = \sum_{d\mid n}g(n)$， 那么有 $g(n) = \sum_{d \mid n}\mu(d)f(\frac{n}{d})$ 。

这种形式下，数论函数 $f(n)$ 称为数论函数 $g(n)$ 的莫比乌斯变换，数论函数 $g(n)$ 称为数论函数 $f(n)$ 的莫比乌斯逆变换（反演）。

容易看出，数论函数 $g(n)$ 的莫比乌斯变换，就是将数论函数 $g(n)$ 与常数函数 $1$ 进行狄利克雷卷积。

(PS.根据狄利克雷卷积与狄利克雷生成函数的对应关系，数论函数 $g(n)$ 的莫比乌斯变换对应的狄利克雷生成函数，就是数论函数 $g(n)$ 的狄利克雷生成函数与黎曼函数 $\zeta$ 的乘积。

形式二：如果有 $f(n) = \sum_{n \mid d}g(d)$ ，那么有 $g(n) = \sum_{n \mid d}\mu(\dfrac{d}{n})f(d)$ 。

证明：

法一：对原式做数论变换。

$\displaystyle \sum_{d \mid n}\mu(d)f(\frac{n}{d}) = \sum_{d \mid n}\mu(d)\sum_{k \mid \frac nd}g(k) =\sum_{k \mid n}g(k)\sum_{d \mid \frac nk}\mu(d) = g(n)$

用 $\sum_{d \mid n}\mu(d)f(\frac nd)$， 再变换求和顺序。最后一步变换的依据： $\sum_{d \mid n} \mu(d) = \left[ n = 1\right]$ ，因此在 $\frac nk = 1$ 时第二个和式的值才为 $1$ 。此时 $n = k$ ，故原式等价于 $\displaystyle \sum_{k\mid n}\left[n = k\right]\cdot g(k) = g(n)$

法二：运用卷积。

原问题为：已知 $f = g * 1$ ， 证明 $g = f * \mu$

易知如下转化：$f * \mu = g * 1 * \mu \implies f\ast\mu = g$ （其中 $1 * \mu = \varepsilon$ ）

对于第二种形式：

类似上面的方法一，我们考虑逆推这个式子。

$\begin{aligned} &\sum_{n \mid d}{\mu(\frac{d}{n})f(d)} \\=& \sum_{k = 1}^{+\infty}{\mu(k)f(kn)} = \sum_{k = 1} ^ {+\infty}{\mu(k)\sum_{kn \mid d}{g(d)}} \\ =& \sum_{n \mid d}{g(d)\sum_{k \mid \frac{d}{n}}{\mu(k)}} = \sum_{n \mid d}{g(n)\epsilon(\frac{d}{n})} \\= & g(n) \end{aligned}$

我们把 $d$ 表示为 $kn$ 的形式，然后把 $f$ 的原定义代入式子。

发现枚举 $k$ 再枚举 $kn$ 的倍数可以转换为直接枚举 $n$ 的倍数再求出 $k$ ，发现后面那一块其实就是 $\epsilon$ , 整个式子只有在 $d = n$ 的时候才能取到值。

QED.

实战例题

Problem B

$\sum_{d = 1}^{\min\left( \lfloor \frac nk \rfloor ,\lfloor \frac mk \rfloor\right)} \mu(d) \lfloor\frac n{kd}\rfloor\lfloor\frac m{kd}\rfloor$

YY的GCD

$\sum_{T = 1}^n \lfloor\frac nT\rfloor*\lfloor\frac mT\rfloor \sum_{k \mid T, k \in prime}\mu(\dfrac{T}{k})$

数字表格

$\prod_{T =1}^n(\prod_{d \mid T}f(d)^{\mu(\frac Td)})^{\lfloor\frac nT\rfloor\cdot\lfloor\frac mT\rfloor}$