莫比乌斯反演学习笔记（一）

· · 个人记录

前置技能

下面先不加说明或证明地给出如下内容：

Ⅰ.莫比乌斯函数 \mu满足\mu(n) =

关于如何通过筛法求得 \mu函数值，通过理解上述定义即可实现，这里不赘述，代码如下：

mu[1] = 1;
for (int i = 2; i <= n; i++) p[i] = 1;
for (int i = 2; i <= n; i++) {
    if (p[i]) pri[c++] = i, mu[i] = -1;
    int d;
    for (int j = 0; j < c && (d = i * pri[j]) <= n; j++) {
        p[d] = 0;
        if (i % pri[j] == 0) { mu[d] = 0; break; }
        else mu[d] = -mu[i];
    }
}

Ⅱ.单位函数 \epsilon满足 \epsilon(n) =

Ⅲ.定义两个数论函数 f(x), g(x)的 \rm Dirichlet卷积（记作 (f * g)(x)）为：

(f * g)(n) = \sum_{d | n}{f(d) g(\frac{n}{d})} + 交换律：$f * g = g * f

莫比乌斯反演

引理

首先给出如下引理：\sum_{d | n}{\mu(d) = \epsilon(n)} 即 \sum_{d | n}{\mu(d) = [n = 1]}或写成卷积形式为 \mu * 1 = \epsilon

证明：

当 n = 1时 \mu(1) = 1，成立。考虑其他的 n。设 n = p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k}，n的因子 d = p_1^{x_1}p_2^{x_2}p_3^{x_3}...p_k^{x_k}。由于当存在平方质因子时 \mu = 0，所以只用考虑每个 x_i为 0或 1的情况。

设 d中有 r个 x_i满足 x_i = 1，那么有

\sum_{d | n}{\mu(d)} = \sum_{r = 0}^{k}{C_{k}^{r}(-1)^r}

根据二项式定理：

(x + y) ^ n = \sum_{r = 0}^{n}{C_n^rx^{n-r}y^r}

当 x = 1, y = -1时，代入原式，有：

\sum_{d | n}{\mu(d)} = (1-1)^k = 0

莫比乌斯反演公式

接下来将给出莫比乌斯反演的公式：

若数论函数 f(n),g(n)满足f(n) = \sum_{d | n}{g(d)}

那么有 g(n) = \sum_{d | n}{\mu(d)f(\frac{n}{d})}

即 f = g * 1 \Rightarrow g = \mu * f，其中 1是函数值恒为 1的常值函数。

证明：

一种较简单的证明是利用 \rm Dirichlet卷积，将 f = g * 1两边同时卷上 \mu，得 \mu * f = g * \mu * 1由于 \mu * 1 = \epsilon，因此\mu * f = g * \epsilon = g

另外的一个常用的公式如下：

若数论函数 f(n), g(n)满足 f(n) = \sum_{n | d}{g(d)}

那么有 g(n) = \sum_{n | d}{\mu(\frac{d}{n})f(d)}

证明：

将 g(n)作如下变形即可：

g(n) = \sum_{n | d}{g(d) * [\frac{d}{n} = 1]} = \sum_{n | d}\left(g(d)\sum_{d'|\frac{d}{n}}{\mu(d')}\right) = \sum_{n | d}\left(\mu(\frac{d}{n})\sum_{d|d'}{g(d')}\right) = \sum_{n | d}{\mu(\frac{d}{n})f(d)}

上述形式和以下的形式是一样的：

若 f(i) = \sum_{d = 1}^{\lfloor{\frac{n}{i}}\rfloor}{g(d * i)}

那么有

g(i) = \sum_{d = 1}^{\lfloor{\frac{n}{i}}\rfloor}{\mu(d)f(d * i)}

例题

1.\rm HDU1695

题意：给定 n, m, k，求 {\rm gcd}(x, y) = k且 x \in [1, n], y \in [1, m]的 (x, y)对数。注意： (x, y)与 (y, x)不重复计算。

分析：我们先忽略 (x, y)与 (y, x)不重复计算的条件，如果直接计算 {\rm gcd}(x, y) = k且 x \in [1, n], y \in [1, m]的 (x, y)对数应如何解决。

首先为了普遍性，规定 n \leq m，下同。

不妨设 g(k)为 {\rm gcd}(x, y) = k的 (x, y)对数， f(k)为满足 k | {\rm gcd}(x, y)的 (x, y)对数，那么有：

f(k) = \sum_{d = 1}^{\lfloor{\frac{n}{k}}\rfloor}{g(d * k)}

利用莫比乌斯反演公式可得：

g(k) = \sum_{d = 1}^{\lfloor{\frac{n}{k}}\rfloor}{\mu(d)f(d * k)}

注意到由于满足 k | {\rm gcd}(x, y)的 (x, y)对数是可以直接计算的，它要求 x, y是 k的倍数，因此有

f(k) = \lfloor{\frac{n}{k}}\rfloor\lfloor{\frac{m}{k}}\rfloor

代入得

g(k) = \sum_{d = 1}^{\lfloor{\frac{n}{k}}\rfloor}{\mu(d)\lfloor{\frac{n}{dk}}\rfloor\lfloor{\frac{m}{dk}}\rfloor} 接下来考虑 $(x, y)$与 $(y, x)$不重复计算的条件。注意到如果数对 $(x, y)$满足 $x \leq n$且 $n <y \leq m$时是不会再计算 $(y, x)$的，因此会被重复计算的 $(x, y)$一定满足 $x \leq n$且 $y \leq n$，故我们用 $n, m$计算得到的答案减去用 $n, n$计算得到答案的一半即得到了不重复的 $n, m$的答案。 代码： ```cpp #include <cstdio> #include <algorithm> using namespace std; const int maxn = 1e5 + 10; typedef long long LL; LL ans = 0; int T, p[maxn], mu[maxn], pri[maxn], g, a, b, c, d, k, kase = 1; LL f(int x, int y, int k) { if (x > y) swap(x, y); x /= k, y /= k; LL ans = 0; for (int i = 1; i <= x; i++) ans += 1LL * mu[i] * (x / i) * (y / i); return ans; } int main() { int n = 1e5; mu[1] = 1; for (int i = 2; i <= n; i++) p[i] = 1; for (int i = 2; i <= n; i++) { if (p[i]) pri[g++] = i, mu[i] = -1; int d; for (int j = 0; j < g && (d = i * pri[j]) <= n; j++) { p[d] = 0; if (i % pri[j] == 0) { mu[d] = 0; break; } else mu[d] = -mu[i]; } } scanf("%d", &T); while (T--) { scanf("%d%d%d%d%d", &a, &b, &c, &d, &k); if (b > d) swap(b, d); if (!k) printf("Case %d: 0\n", kase++); else printf("Case %d: %lld\n", kase++, f(b, d, k) - f(b, b, k) / 2); } return 0; } ``` 然而，值得注意的是，此题存在着更快的分块解法。 首先，给出如下结论：$\lfloor{\frac{n}{d}}\rfloor$最多只会有 ${\rm O}(\sqrt n)$个取值。 证明显然： + 当 $1 \leq d \leq \sqrt n$时，$d$只有 $\sqrt n$个取值，该条件下 $\lfloor{\frac{n}{d}}\rfloor$最多只有 $\sqrt n$个取值。 + 当 $\sqrt n \leq d \leq n$时，$\lfloor{\frac{n}{d}}\rfloor \leq \sqrt n$，该条件下 $\lfloor{\frac{n}{d}}\rfloor$最多只有 $\sqrt n$个取值。 同理，$\lfloor{\frac{m}{d}}\rfloor$最多只会有 ${\rm O}(\sqrt m)$个取值，由于取值的区间是连续的，因此 $\lfloor{\frac{n}{d}}\rfloor\lfloor{\frac{m}{d}}\rfloor$最多有 ${\rm O}(\sqrt n + \sqrt m)$个取值。 观察最开始的式子 $$g(k) = \sum_{d = 1}^{\lfloor{\frac{n}{k}}\rfloor}{\mu(d)\lfloor{\frac{n}{dk}}\rfloor\lfloor{\frac{m}{dk}}\rfloor}$$ 如果我们把右边的 $\lfloor{\frac{n}{dk}}\rfloor\lfloor{\frac{m}{dk}}\rfloor$看做定值，由于每一个 $\lfloor{\frac{n}{dk}}\rfloor\lfloor{\frac{m}{dk}}\rfloor$对应的是一段连续的区间，因此左侧其实是两个 $\mu$函数的前缀和之差。 现在关键在于如何高效地找出值 $\lfloor{\frac{n}{dk}}\rfloor\lfloor{\frac{m}{dk}}\rfloor$所对应的区间。即对于一个数 $i$，如何找出最大的 $j$，使得 $\lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{i}}\rfloor = \lfloor{\frac{n}{j}}\rfloor\lfloor{\frac{m}{j}}\rfloor$。我们先单个考虑：如何找出满足 $\lfloor{\frac{n}{i}}\rfloor = \lfloor{\frac{n}{j}}\rfloor$的最大的 $j$。 可以取掉右边的向下取整，得到 $$\lfloor{\frac{n}{i}}\rfloor = \frac{n}{j}$$ 变形得到 $$j = \lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor$$ 这是满足 $\lfloor{\frac{n}{i}}\rfloor = \lfloor{\frac{n}{j}}\rfloor$的最大的 $j$。同理可求满足 $\lfloor{\frac{m}{i}}\rfloor = \lfloor{\frac{m}{j}}\rfloor$的最大的 $j$，因此满足 $\lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{i}}\rfloor = \lfloor{\frac{n}{j}}\rfloor\lfloor{\frac{m}{j}}\rfloor$的最大的 $j$为： $${\rm min}\left(\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor, \lfloor{\frac{m}{\lfloor{\frac{m}{i}}\rfloor}}\rfloor\right)$$ 转述成代码，即`min(n / (n / i), m / (m / i))`。 通过预处理 $\mu$前缀和，便可以写出该题更高效的代码。 ```cpp #include <cstdio> #include <algorithm> using namespace std; const int maxn = 1e5 + 10; typedef long long LL; LL ans = 0; int T, p[maxn], mu[maxn], pri[maxn], g, a, b, c, d, k, kase = 1; LL f(int x, int y, int k) { if (x > y) swap(x, y); x /= k, y /= k; LL ans = 0; for (int i = 1, last; i <= x; i = last + 1) { last = min(x / (x / i), y / (y / i)); ans += 1LL * (mu[last] - mu[i - 1]) * (x / i) * (y / i); } return ans; } int main() { int n = 1e5; mu[1] = 1; for (int i = 2; i <= n; i++) p[i] = 1; for (int i = 2; i <= n; i++) { if (p[i]) pri[g++] = i, mu[i] = -1; int d; for (int j = 0; j < g && (d = i * pri[j]) <= n; j++) { p[d] = 0; if (i % pri[j] == 0) { mu[d] = 0; break; } else mu[d] = -mu[i]; } } for (int i = 1; i <= n; i++) mu[i] += mu[i - 1]; scanf("%d", &T); while (T--) { scanf("%d%d%d%d%d", &a, &b, &c, &d, &k); if (b > d) swap(b, d); if (!k) printf("Case %d: 0\n", kase++); else printf("Case %d: %lld\n", kase++, f(b, d, k) - f(b, b, k) / 2); } return 0; } ``` 完成此题之后，可以顺带解决 $\rm P2522$，该题变成了真正意义上的求满足 $x \in [a, b], y \in [c, d]$的 ${\rm gcd}(x, y) = k$的对数，但 $(x, y)$与 $(y, x)$都会被计算。 利用容斥原理计算即可，答案即为`f(b, d, k) - f(a - 1, d, k) - f(b, c - 1, k) + f(a - 1, c - 1, k)`。代码如下： ```cpp #include <cstdio> #include <algorithm> using namespace std; const int maxn = 5e4 + 10; typedef long long LL; LL ans = 0; int T, p[maxn], mu[maxn], pri[maxn], g, a, b, c, d, k; LL f(int x, int y, int k) { if (x > y) swap(x, y); x /= k, y /= k; LL ans = 0; for (int i = 1, last; i <= x; i = last + 1) { last = min(x / (x / i), y / (y / i)); ans += 1LL * (mu[last] - mu[i - 1]) * (x / i) * (y / i); } return ans; } int main() { int n = 5e4; mu[1] = 1; for (int i = 2; i <= n; i++) p[i] = 1; for (int i = 2; i <= n; i++) { if (p[i]) pri[g++] = i, mu[i] = -1; int d; for (int j = 0; j < g && (d = i * pri[j]) <= n; j++) { p[d] = 0; if (i % pri[j] == 0) { mu[d] = 0; break; } else mu[d] = -mu[i]; } } for (int i = 1; i <= n; i++) mu[i] += mu[i - 1]; scanf("%d", &T); while (T--) { scanf("%d%d%d%d%d", &a, &b, &c, &d, &k), a--, c--; printf("%lld\n", f(b, d, k) - f(a, d, k) - f(b, c, k) + f(a, c, k)); } return 0; } ``` $2. \rm P2257

给定 n, m，计算 \sum_{x = 1}^{n}\sum_{y = 1}^{m}[{\rm gcd}(x, y) = prime] 即有多少对 (x, y)满足 x \in [1, n], y \in [1, m]且 {\rm gcd}(x, y)为质数。

有了上题的经验，一种很直接的做法就是直接枚举所有的质数 p，将所有满足 {\rm gcd}(x, y) = p的 (x, y)对数加起来即为答案。很可惜，这样会超时。

我们将式子写具体一点，我们要求的是

\sum_{p:\ p = prime, p \leq n}\sum_{d = 1}^{\lfloor{\frac{n}{p}}\rfloor}{\mu(d)\lfloor{\frac{n}{dp}}\rfloor\lfloor{\frac{m}{dp}}\rfloor}

在上一个题中，我们将右边的 \lfloor{\frac{n}{dp}}\rfloor\lfloor{\frac{m}{dp}}\rfloor看做定值，通过分块，利用前缀和直接计算左侧变值，幸运的是，本题我们依然可以这么做。

直接用上述式子似乎不好观察，我们换一个形式：

\sum_{p:\ p = prime, p \leq n}\sum_{p|d}\mu(\frac{d}{p})\lfloor{\frac{n}{d}}\rfloor\lfloor{\frac{m}{d}}\rfloor

现在我们不考虑对单个质数进行式子求和，而是整体分析所有的 d，那么上述式子和下式是等价的：

\sum_{d = 1}^{n}{\left(\sum_{p|d}{\mu(\frac{d}{p})\lfloor{\frac{n}{d}}\rfloor\lfloor{\frac{m}{d}}\rfloor}\right)}

利用该公式，预求出每一个 d对应的 \sum_{p|d}{\mu(\frac{d}{p})}，便又可以利用分块来实现。此题至此得以解决。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1e7 + 10;
typedef long long LL;

int T, n, m, g, mu[maxn], p[maxn], pri[maxn], sum[maxn];

LL f(int x, int y) {
    if (x > y) swap(x, y);
    LL ans = 0;
    for (int i = 1, last; i <= x; i = last + 1) {
        last = min(x / (x / i), y / (y / i));
        ans += 1LL * (sum[last] - sum[i - 1]) * (x / i) * (y / i);
    }
    return ans;
}

int main() {
    int c = 1e7;
    mu[1] = 1;
    for (int i = 2; i <= c; i++) p[i] = 1;
    for (int i = 2; i <= c; i++) {
        if (p[i]) pri[g++] = i, mu[i] = -1;
        int d;
        for (int j = 0; j < g && (d = i * pri[j]) <= c; j++) {
            p[d] = 0;
            if (i % pri[j] == 0) { mu[d] = 0; break; }
            else mu[d] = -mu[i];
        }
    }
    for (int i = 0; i < g; i++) for (int j = 1; pri[i] * j <= c; j++) sum[pri[i] * j] += mu[j];
    for (int i = 1; i <= c; i++) sum[i] += sum[i - 1];
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        printf("%lld\n", f(n, m));
    }
    return 0;
}

下一篇链接