数论

莫比乌斯反演

Posted by Monad on July 24, 2018

引入

首先，我们有一个公式：$ F(n) = \sum_{d|n} G(d) $。然后我们可以通过 G 来算出 F。例如 $F(6) = G(1) + G(2) + G(3) + G(6)$。
如果我们可以算出 F 的值，那我们可以通过 F 来推出 G。
根据定义，可得：

  • $ G(1) = F(1) $
  • $ G(2) = F(2) - F(1) $
  • $ G(3) = F(3) - F(1) $
  • $ G(4) = F(4) - F(2) $
  • $ G(5) = F(5) - F(1) $
  • $ G(6) = F(6) - F(3) - F(2) + F(1) $

通过观察，我们可以发现对于每一个 G(n)，等于一系列的 F(d) 相加减，并且 d 是 n 的约数。
所以我们就可以枚举这个约数 d，然后让 F(d) 乘上一个系数（-1, 0 或 1），然后求和，就可以得到 G(n) 啦！
那么现在的问题就是，这个系数如何确定呢？

$ \mu $

考虑简单情况：如果 $ n = p^k $，且 p 是质数，求 G(n)。

因为 $ n = p^k $，那么 n 的约数就是 $1$, $p^1$, $p^2$, $p^3$, $\cdots$, $p^k$。

则

$$ F(p^k) = G(1) + G(p^1) + G(p^2) + \cdots + G(p^k) \tag{1} $$

同时也可以得到

$$ F\left(\frac{n}{p}\right) = F(p^{k-1}) = G(1) + G(p^1) + G(p^2) + \cdots + G(p^{k-1}) \tag{2} $$

由 1 - 2，得

$$ G(n) = F(n) - F(\frac{n}{p}) \tag{3} $$

然后再考虑一下更复杂的情况：

设 $ n = p_1^{c_1} p_2^{c_2} $，其中 $p_1$ 和 $p_2$ 是不同的质数。

那么 n 的约数就是 $ p_1^x p_2^y $，其中 $ x \leq c_1, y \leq c_2 $。

则

$$ F(n) = \sum_{x=1}^{c_1} \sum_{y=1}^{c_2} G(p_1^x p_2^y) \tag{4} $$

由容斥原理，可得

$$ G(n) = F(n) - F(\frac{n}{p_1}) - F(\frac{n}{p_2}) + F(\frac{n}{p_1 p_2}) \tag{5} $$

最后我们推广到任意一个 n，则 $ n = p_1^{c_1} p_2^{c_2} p_3^{c_3} \cdots p_k^{c_k} $。同样，由容斥原理可得

$$ G(n) = F(n) - F(\frac{n}{p_1}) - F(\frac{n}{p_2}) - \cdots + F(\frac{n}{p_1 p_2}) + F(\frac{n}{p_1 p_3}) + \cdots - F(\frac{n}{p_1 p_2 p_3}) \tag{6} $$

设每一项为 $ F(\frac{n}{d}) $，可发现系数只与 d 有关，则设这个系数为 $ \mu(d) $，$ \mu(d) $ 即莫比乌斯函数。

  1. 首先由 6 可得，如果 d 是由 k 个质因数组成的，那么有 $ \mu(d) = (-1)^k $，显然 $ \mu(1) = 1 $

  2. 然后如果 d 不是由不同的质数相乘得到的，即 d 的某个质因数的次数大于 1，显然这一项并不存在，即 $ \mu(d) = 0 $

于是我们就得到了莫比乌斯反演公式：

$$ F(n) = \sum_{d|n} G(n) \Leftrightarrow G(n) = \sum_{d|n} \mu(d)F(\frac{n}{d}) \tag{7} $$

同时也得到了莫比乌斯函数 $ \mu $ 的定义：

$$ \mu(n) = \begin{cases} 0 & , \exists i \in [1, k],\, c_i > 1 \\ (-1)^k & , \forall i \in [1, k],\, c_i = 1 \end{cases} \tag{8} $$

线性筛求 $ \mu $

因为 $ \mu $ 是积性函数，所以我们可以使用线性筛来求。
要把它嵌入至线性筛中，无非要考虑这几种情况：k 是质数、i % prime[j] == 0 和 i % prime[j] != 0 这三种情况而已。

  1. 如果 k 是质数，那么显然 $ \mu(k) = -1 $；
  2. 如果 i % prime[j] == 0，那么说明 k 中含有相同的质因数，因此 $ \mu(k) = 0 $；
  3. 如果 i % prime[j] != 0，根据 $\mu$ 是积性函数，因此 $ \mu(k) = -\mu(i) $。

然后我们就可以线性筛了。

$ \mu $ 的性质

$$ \sum_{d|n} \mu(d) = [n = 1] \tag{9} $$

用人话说就是 n 所有约数的 $\mu$ 的和为 0（当 n == 1 时和为 1）。
证明：略，把 $\mu$ 的定义带入即可。

应用

应用的话，一般来说由两种方法：

  1. 用莫比乌斯反演，构造一个符合反演公式的式子，但是比较复杂；
  2. 利用莫比乌斯函数的性质。

例题

求 $ \sum_{i=1}^{n} \sum_{j=1}^{n} gcd(i,j) $。

求 gcd 很不方便，不利于公式的化简。我们可以枚举 gcd(i, j) 的值 d。则设 i = dx, j = dy，且 i, j 的范围都是 $ 1 \sim \floor{ \frac{n}{d} } $，注意还要满足 gcd(x, y) == 1 哦。

$$ \sum_{d=1}^{n} \sum_{x=1}^{ \floor{ \frac{n}{d} } } \sum_{y=1}^{ \floor{ \frac{n}{d} } } d \, [ \, gcd(x, y) = 1] \tag{10} $$

可以看到 d 与 i, j 无关，所以我们可以把它提取出来。

$$ \sum_{d=1}^{n} d \sum_{x=1}^{ \floor{ \frac{n}{d} } } \sum_{y=1}^{ \floor{ \frac{n}{d} } } [ gcd(x, y) = 1] \tag{11} $$

考虑莫比乌斯函数的性质（9），把 $ [ gcd(x, y) ] $ 代入 $ \sum_{d|n} \mu(d) = [n = 1] $，得

$$ \sum_{d=1}^{n} d \sum_{x=1}^{ \floor{ \frac{n}{d} } } \sum_{y=1}^{ \floor{ \frac{n}{d} } } \sum_{q | gcd(x, y)} \mu(q) \tag{12} $$

再考虑 $ q | gcd(x, y) $ 的意义，可得 $ q | gcd(x, y) \Leftrightarrow q | x, q | y $。

然后设 $ x = qx' $, $ y = qy' $，然后枚举 q，得

$$ \sum_{d=1}^{n} d \sum_{q=1}^{\floor{ \frac{n}{d} }} \mu(q) \sum_{x'=1}^{ \floor{ \frac{n}{dq} } } \sum_{y'=1}^{ \floor{ \frac{n}{dq} } } 1 \tag{13} $$

化简，得

$$ \sum_{d=1}^{n} d \sum_{q=1}^{\floor{ \frac{n}{d} }} \mu(q) \floor{ \frac{n}{dq} }^2 \tag{14} $$

实现

这个程序怎么实现呢？

我们可以先预处理内层部分，则

$$ f(n) = \sum_{i=1}^{n} \mu(i) \floor{ \frac{n}{i} }^2 \tag{15} $$

考虑分块。当我们从 1 枚举到 n 时，$ \floor{ \frac{n}{i} } $ 只有 $ 2 \sqrt{n} $ 种取值。证明：

  1. 当 $ i \leq \sqrt{n} $ 时，显然最多有 $ \sqrt{n} $ 种取值；
  2. 当 $ i > \sqrt{n} $，$ \frac{n}{i} \leq \sqrt{n} $，所以此时只有 $ \sqrt{n} $ 种取值。

所以 $ \floor{ \frac{n}{i} } $ 只有 $ 2 \sqrt{n} $ 种取值，我们可以把取值相同的 $ \floor{ \frac{n}{i} } $ 一并计算即可，此时的 $ \mu(i) $ 用前缀和统计即可。

我们从 i 从 1 枚举，要考虑的问题就是对于一个 i，如何求出一个最大的 j，且 $ \floor{ \frac{n}{i} } = \floor{ \frac{n}{j} } $。

考虑它们具有相同的取值，显然，$ j = \floor{ \frac{n}{ \floor{ \frac{n}{i} } } } $。

代码实现：

long long get_f(const int n) {
	long long ans = 0;
	for (int i=1, j=0; i<=n; i=j+1) {
		j = n / (n / i);
		ans += (long long)(sum[j] - sum[i-1]) * (n / i) * (n / i);
	}
	return ans;
}

把内层搞完之后，我们要回到原式。将 $ f(n) $ 代入 (14)，得

$$ \sum_{d=1}^{n} d f(\floor{ \frac{n}{d} }) \tag{16} $$

然后这里又可以分块处理。意不意外？高不高兴？开不开心？

这里的代码实现：

long long ans = 0;
for (int i=1, j=0; i<=n; i=j+1) {
	j = n / (n / i);
	ans += (long long)(j - i + 1) * (j + 1) / 2 * get_f(n / i);
}

每一层的时间复杂度都是 $ O(\sqrt{n}) $，所以总的时间复杂度是 $ O(n) $。

一些小技巧

如果求 $ \sum_{i=1}^{n} \sum_{j=1}^{m} gcd(i,j) $，$ n \leq m $ 怎么办？

前面照常化简，d, q 的上界由 n（较小值）决定，可以化简到这里：

$$ \sum_{d=1}^{n} d \sum_{q=1}^{\floor{ \frac{n}{d} }} \mu(q) \floor{ \frac{n}{dq} } \floor{ \frac{m}{dq} } \tag{17} $$

然后我们如何分块呢？

这里 $ \floor{ \frac{n}{dq} } $ 和 $ \floor{ \frac{m}{dq} } $ 的取值数量都只有 $ O(\sqrt{n}) $ 的级别。

我们可以把相同的 $ \floor{ \frac{n}{dq} } $ 和 $ \floor{ \frac{m}{dq} } $ 一起计算即可。j 取两个范围的最小值，即：

j = min(n / (n / i), m / (m / i));
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：莫比乌斯反演”
CATALOG
    FRIENDS