莫比乌斯反演笔记

Link_Cut_Y · 2023-06-17 19:46:13 · 算法·理论

1. 莫比乌斯函数

设正整数 n 的标准分解为 \sum \limits_{i = 1}^{k} p_i^{c_i}。

莫比乌斯函数定义为 \mu(n) = \left\{\begin{matrix} 0 \qquad \exists i \in [1, k], c_i \gt 0 \\ (-1) ^ k \qquad \text{otherwise} \end{matrix}\right.

重要结论 1: \sum \limits_{d | n}^{} \mu(d) = [n = 1] 。该结论可以用莫比乌斯函数性质证明。

重要结论 2: 莫比乌斯函数是积性函数，即对于 p \perp q，有 \mu (pq) = \mu(p) \mu(q)。

2. 狄利克雷卷积

1. 一些常见的数论积性函数：

莫比乌斯函数 \mu (n)。
欧拉函数 \varphi(n)：1 \sim n 中与 n 互质的数的个数。
约数个数 d(n)：n 的约数个数。
约数和 \sigma：\sum \limits_{d | n}^{} d。
元函数 \epsilon(n)。即 [n = 1]。
单位函数 \text{id}(n)。即为 n。
恒等函数 \text{I}(n)。该函数恒为 1。有时也写作 1。

其中后三个函数为完全积性函数。

2. 狄利克雷卷积

定义两个数论函数的狄利克雷卷积为 (f * g)(n) = \sum \limits_{d | n} f(d) g(\dfrac{n}{d})，读作 f 卷 g。

其中后面括号里的 n 代表卷积范围。

卷积有下面这些良好的性质：

交换律：f * g = g * f。
结合律：(f * g) * h = f * (g * h)。

上面的性质可以根据卷积定义证明。这里略过。

3. 常见数论函数的狄利克雷卷积

d = 1 * 1

证明：1 * 1 = \sum \limits_{d | n}^{} 1 \times 1 = d(n)。

\epsilon = \mu * 1

上文提到过，\sum \limits_{d | n} \mu = [n = 1] = \epsilon(n)。

\text{id} = \varphi * 1
利用欧拉函数性质证明。
\text{(1)}$ $\varphi(1) = 1 \text{(2)}$ $\varphi(p) = p - 1 \text{(3)}$ $\varphi(p ^ 2) = p \times \varphi(p) = p ^ 2 - p \text{(4)}$ 根据性质 $(3)$，推出 $\varphi(p ^ k) = \varphi(p) \times p^{k - 1} = p ^ k - p ^{k - 1} (5)$ $\sum \limits_{i = 0}^{c} \varphi(p ^ i) = 1 + \sum \limits_{i = 1}^{c} \varphi(p ^ i) = 1 + \sum \limits_{i = 1}^{c} p ^ i - p^{i - 1} = p ^ c
\varphi = \mu * \text{id}
证明：由于 \text{id} = \varphi * 1，根据卷积的性质，可以在等式两边同时卷上 \mu，得到 \text{id} * \mu = \varphi * 1 * \mu。根据 \mu * 1 = \epsilon 得 \text{id} * \mu = \varphi * \epsilon = \varphi。证毕。
\sigma = \text{id} * 1

证明：\sigma(n) = \sum \limits_{d | n} d = \sum \limits_{d | n} \text{id}(d) \times I(\dfrac{n}{d}) = \text{id} * 1(n)。

3. 莫比乌斯反演

莫比乌斯反演的形式如下：

如果存在 F(n) = \sum \limits_{d | n} f(d)，那么有 f(n) = \sum \limits_{d | n} F(d) \mu(\dfrac{n}{d})。

该结论可以利用狄利克雷卷积来证明。

证明：

### 某些例题：下面求和的上界省略了下取整符号。 [$\text{P3455 [POI2007]ZAP-Queries}$](https://www.luogu.com.cn/problem/P3455) 求 $\sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{m} [(i, j) = k]$。大力莫反。 $$\begin{array}{c} \sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{m} [(i, j) = k] \\\\ = \sum \limits_{i = 1}^{\frac{n}{k}}\sum \limits_{j = 1}^{\frac{m}{k}} [(i, j) = 1] \\\\ = \sum \limits_{i = 1}^{\frac{n}{k}}\sum \limits_{j = 1}^{\frac{m}{k}} \mu((i, j)) * 1 \\\\ = \sum \limits_{i = 1}^{\frac{n}{k}}\sum \limits_{j = 1}^{\frac{m}{k}} \sum \limits_{d | (i, j)} \mu(d) \\\\ = \sum \limits_{d = 1}^{n} \mu(d) \sum \limits_{i = 1}^{\frac{n}{kd}} \sum \limits_{j = 1}^{\frac{m}{kd}} 1 \\\\ = \sum \limits_{d = 1}^{n} \mu(d) \left \lfloor \dfrac{n}{kd} \right \rfloor \left \lfloor \dfrac{m}{kd} \right \rfloor \end{array}$$ 前面的 $\mu$ 可以线筛，后面的可以整除分块套上 $\mu$ 前缀和。 [$\text{P2522 [HAOI2011]Problem b}$](https://www.luogu.com.cn/problem/P2522) 求 $\sum \limits_{i = a}^{b} \sum \limits_{j = c}^{d} [(i, j) = k]$。上一道题的强化版。将上一道题写成函数 $\operatorname{calc(n, m, k)}$，表示求求 $\sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{m} [(i, j) = k]$ 的值。然后利用类似二维前缀和的方式，计算出答案即为 $\operatorname{calc(b, d, k)} - \operatorname{calc(a - 1, d, k)} - \operatorname{calc(c - 1, b, k)} + \operatorname{calc(a - 1, c - 1, k)}

\text{P1390 公约数的和}

\sum_{i = 1}^n \sum_{j = i + 1}^n (i, j)

首先考虑计算 \sum \limits_{i = 1}^n \sum \limits_{j = 1}^n (i, j)。

首先枚举 (i, j)，得到 \sum \limits_{d = 1}^{n} d \sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{n} [(i, j) = d]

继续化简：

\begin{array}{c} \sum \limits_{d = 1}^{n} d \sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{n} [(i, j) = d] \\\\ = \sum \limits_{d = 1}^{n} d \sum \limits_{i = 1}^{\frac{n}{d}} \sum \limits_{j = 1}^{\frac{n}{d}} [(i, j) = 1] \\\\ = \sum \limits_{d = 1}^{n} d \sum \limits_{i = 1}^{\frac{n}{d}} \sum \limits_{j = 1}^{\frac{n}{d}} \mu * 1(\gcd(i, j)) \\\\ = \sum \limits_{d = 1}^{n} d \sum \limits_{i = 1}^{\frac{n}{d}} \sum \limits_{j = 1}^{\frac{n}{d}} \sum \limits_{p | (i, j)} \mu(p) \\\\ = \sum \limits_{d = 1}^{n} d \sum \limits_{p = 1}^{n} \mu(p) \sum \limits_{i = 1}^{\frac{n}{pd}} \sum \limits_{j = 1}^{\frac{n}{pd}} 1\\\\ = \sum \limits_{d = 1}^{n} d \sum \limits_{p = 1}^{\frac{n}{d}} \mu(p) \left \lfloor \dfrac{n}{pd} \right \rfloor \left \lfloor \dfrac{n}{pd} \right \rfloor \\\\ \text{令 k = pd，} \sum \limits_{k = 1}^{n} \left \lfloor \dfrac{n}{k} \right \rfloor \left \lfloor \dfrac{n}{k} \right \rfloor \sum \limits_{d | k} d \times \mu(\dfrac{k}{d}) \\\\ \sum \limits_{k = 1}^{n} \left \lfloor \dfrac{n}{k} \right \rfloor \left \lfloor \dfrac{n}{k} \right \rfloor \text{id} * \mu(k) \\\\ \sum \limits_{k = 1}^{n} \left \lfloor \dfrac{n}{k} \right \rfloor \left \lfloor \dfrac{n}{k} \right \rfloor \varphi(k) \end{array}

原题要求的就是刚才求的减去 $\sum i$ 之后在除以 $2$ 。这里根据最大公约数的交换律或者对称性易得。另外，这个题也可以不必卷到 $\varphi$。只要卷到 $= \sum \limits_{d = 1}^{n} d \sum \limits_{p = 1}^{\frac{n}{d}} \mu(p) \left \lfloor \dfrac{n}{pd} \right \rfloor \left \lfloor \dfrac{n}{pd} \right \rfloor$ 就可以套两层整除分块了。这样的复杂度是 $O(n + n) = O(n)$，也很优秀。一天后返回来在看一眼原来推得式子，会发现确实推复杂了。正难则反，直接用 $\varphi * 1 = id$ 来推。 $$ \begin{array}{c} \sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{n} (i, j) \\\\ = \sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{n} \varphi * 1((i,j)) \\\\ = \sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{n} \sum \limits_{d | (i, j)} \varphi(d) \\\\ = \sum \limits_{d = 1}^{n} \varphi(d) \sum \limits_{i = 1}^{\frac{n}{d}} \sum \limits_{j = 1}^{\frac{n}{d}} 1 \\\\ \sum \limits_{d = 1}^{n} \varphi(d) \left \lfloor \dfrac{n}{d} \right \rfloor \left \lfloor \dfrac{n}{d} \right \rfloor \end{array} $$ 可以发现结果是一样的。 [$\text{P2257 YY的GCD}$](https://www.luogu.com.cn/problem/P2257) 设质数集为 $\mathbb{P}$，求： $$\sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{m} [(i, j) \in \mathbb{P}]$$ 又到了愉快的推式子时间：这里设 $n \le m$， $$ \begin{array}{c} \sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{m} [(i, j) \in \mathbb{P}] \\\\ = \sum \limits_{d \in \mathbb{P}}^{} \sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{m} [(i, j) = d] \\\\ = \sum \limits_{d \in \mathbb{P}}^{} \sum \limits_{i = 1}^{\frac{n}{d}} \sum \limits_{j = 1}^{\frac{m}{d}} [(i, j) = 1] \\\\ = \sum \limits_{d \in \mathbb{P}}^{} \sum \limits_{i = 1}^{\frac{n}{d}} \sum \limits_{j = 1}^{\frac{m}{d}} \mu * 1(\gcd(i, j)) \\\\ = \sum \limits_{d \in \mathbb{P}}^{} \sum \limits_{i = 1}^{\frac{n}{d}} \sum \limits_{j = 1}^{\frac{m}{d}} \sum \limits_{p | (i, j)} \mu(p) \\\\ = \sum \limits_{d \in \mathbb{P}}^{} \sum \limits_{p = 1}^{\frac{n}{d}} \mu(p) \sum \limits_{i = 1}^{\frac{n}{pd}} \sum \limits_{j = 1}^{\frac{m}{pd}} 1\\\\ = \sum \limits_{d \in \mathbb{P}}^{} \sum \limits_{p = 1}^{\frac{n}{d}} \mu(p) \left \lfloor \dfrac{n}{pd} \right \rfloor \left \lfloor \dfrac{m}{pd} \right \rfloor \\\\ \text{令 k = pd，} \sum \limits_{k = 1}^{n} \left \lfloor \dfrac{n}{k} \right \rfloor \left \lfloor \dfrac{m}{k} \right \rfloor \sum \limits_{d | k, d \in \mathbb{P}} \mu(\dfrac{k}{d}) \\\\ \end{array} $$ 然后发现两个下取整可以直接整除分块，瓶颈就在计算 $\sum \limits_{d | k, d \in \mathbb{P}} \mu(\dfrac{k}{d})$ 上。这个玩意可以筛出质数后预处理。预处理复杂度 $O(n + n \log \log n)$，计算复杂度 $O(T \sqrt n)$。总复杂度 $O(n + n \log \log n + T \sqrt n)$。看了一下题解，预处理也可以线性筛。不过不想看了，反正能过就行。 ```cpp void init() { mu[1] = 1; for (int i = 2; i <= N - 5; i ++ ) { if (!is_prime[i]) p[ ++ cnt] = i, mu[i] = -1; for (int j = 1; j <= cnt and i * p[j] <= N - 5; j ++ ) { is_prime[i * p[j]] = true; if (i % p[j] == 0) break; mu[i * p[j]] = - mu[i]; } } for (int i = 1; i <= cnt; i ++ ) for (int j = 1; p[i] * j <= N - 5; j ++ ) f[p[i] * j] += mu[j]; for (int i = 1; i <= N - 5; i ++ ) s[i] = s[i - 1] + f[i]; } void substack() { scanf("%lld%lld", &n, &m); if (n > m) swap(n, m); int ans = 0; for (int l = 1, r; l <= n; l = r + 1) { r = min(n / (n / l), m / (m / l)); ans += (n / l) * (m / l) * (s[r] - s[l - 1]); } printf("%lld\n", ans); } ``` [$\text{P3327 [SDOI2015]约数个数和}$](https://www.luogu.com.cn/problem/P3327) 设 $d(x)$ 为 $x$ 的约数个数，给定 $n,m$，求 $$\sum_{i=1}^n\sum_{j=1}^md(ij)$$ 有结论：$d(ij) = \sum \limits_{x | i}^{} \sum \limits_{y | j}^{} [(x, y) = 1]

于是可以愉快地推柿子了。

\begin{array}{c} \sum \limits_{i = 1}^{n} \sum \limits_{j = 1}^{m} \sum \limits_{x | i}^{} \sum \limits_{y | j}^{} [(x, y) = 1] \\\\ = \sum \limits_{x = 1}^{n} \sum \limits_{y = 1}^{m} [(x, y) = 1] \left \lfloor \dfrac{n}{x} \right \rfloor \left \lfloor \dfrac{m}{y} \right \rfloor \\\\ = \sum \limits_{d = 1}^{\min(n, m)} \mu(d) \sum \limits_{x = 1}^{\frac{n}{d}} \sum \limits_{j = 1}^{\frac{m}{d}} \left \lfloor \dfrac{n}{xd} \right \rfloor \left \lfloor \dfrac{m}{yd} \right \rfloor \end{array}

不妨设 f(n) = \sum \limits_{i = 1}^{n} \left \lfloor \dfrac{n}{i} \right \rfloor，可以发现这个玩意就等于 \sum \limits_{i = 1}^{n}d(i)。而这个东西可以筛 \mu 的时候预处理出来。

于是柿子变成 \sum \limits_{d = 1}^{\min(n, m)} \mu(d) f(\dfrac{n}{d}) f(\dfrac{m}{d})。整出分块即可。总复杂度 O(T \sqrt n)。预处理可以用线性筛，但是懒得写了，直接莽了个 O(n \log n) 暴力上去。

void init(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i ++ ) {
        if (!is_prime[i]) p[ ++ cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt and i * p[j] <= n; j ++ ) {
            is_prime[i * p[j]] = true;
            if (i % p[j] == 0) break;
            mu[i * p[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= n; i ++ )
        mu_s[i] = mu_s[i - 1] + mu[i];
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j += i)
            s[j] ++ ;
    for (int i = 1; i <= n; i ++ )
        s[i] += s[i - 1];
}
void substack() {
    scanf("%lld%lld", &n, &m);
    int ans = 0;
    for (int l = 1, r; l <= min(n, m); l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += s[n / l] * s[m / l] * (mu_s[r] - mu_s[l - 1]);
    }
    printf("%lld\n", ans);
}

~~两年半~~两天半，终于把莫反学完了。再次小记，以免自己以后再忘掉。