学习笔记——莫比乌斯反演

前言

莫比乌斯反演是数论内容的一个重要的分支，通常用于求一些不好直接求解的数论函数。

前置知识

若无特别说明，$p$ 表示质数。

积性函数

对于一个数论函数 $f(n)$，如果满足 $f(xy)=f(x)f(y)$，其中$\text{gcd}(x,y)=1$，则称 $f(n)$ 为积性函数。

性质

若 $f(n), g(n)$ 为积性函数，则下列函数均为积性函数。

• $h(n)=f(n)g(n)$
• $h(n)=f(n^p)$
• $h(n)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d})$

常见的积性函数

• $1(n) = 1$
• $\epsilon(n)=[n=1]$ （读作 [ˈepsɪlɑːn]）
• $I(n)=n$
• $id_k(n)=n^k$
• $\sigma_k(n)=\sum_{d|n}d^k$
• $$
  \varphi(n) = n\prod_{p|n}(1-\dfrac{1}{p})
  $$
• $$
  \mu(n)=\begin{cases}
  1&(n=1)\\
  (-1)^k&n=\prod\limits_{i=1}^k p_i\\
  0&(\text{otherwise})
  \end{cases}
  $$

数论分块

对于式子
$$
\sum_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor
$$
可以通过分块的方式在 $O(\sqrt{n})$ 求得。
发现 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 最多有 $ \sqrt{n}$ 种取值，将相同的$\left\lfloor\dfrac{n}{i}\right\rfloor$一起处理，即设当前块左端点为 $L$，则右端点 $R=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{L}\right\rfloor}\right\rfloor$。

代码实现

for (int x = 1, gx; x <= n; x = gx + 1) {
    gx = n / (n / x);
    ans += (gx - x + 1) * (gx + x) / 2 * (n / x);
}

其中 (gx - x + 1) * (gx + x) / 2 为小学学过的公差为 $1$ 等差数列求和。

狄利克雷卷积

对于数论函数 $f,g$ ,其卷积为
$$
(f*g)(n)=\sum_{d|n}f(d)g(\dfrac{n}{d})
$$
且满足

• 交换律 $f\ast g=g\ast f$
• 结合律 $(f\ast g)\ast h=f\ast (g\ast h)$
• 分配律 $f\ast g+f\ast h=f\ast (g+h)$

常见等式

• $\sigma_0=1\ast 1$
• $\sigma_1=I\ast 1$
• $\epsilon=\mu \ast 1$
• $I=\varphi\ast 1$
• $\varphi=I\ast \mu$

定理

$$
f = g \ast 1 \Leftrightarrow g = f \ast \mu
$$
即
$$
f(n) = \sum_{d|n}g(d) \Leftrightarrow g(n)=\sum_{d|n}f(d)\mu(\dfrac{n}{d})
$$

应用

若无特别说明，假定 $n \le m$。

I

多组询问，求
$$
\sum_{i=1}^n\sum_{j=1}^m[\text{gcd}(i,j)=1]
$$
其中 $T \le 10^4, n,m \le 10^7$。

由 $\epsilon=\mu \ast 1$ 可知
$$
= \sum_{i=1}^n\sum_{j=1}^m\sum_{d|\text{gcd}(i,j)}\mu(d)
$$
改变枚举顺序，先枚举 $d$，并由 $d|\text{gcd}(i,j)$ 可知，$d|i$ 且 $d|j$，则
$$
= \sum_{d=1}^n\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}1
$$

$$
=\sum_{d=1}^n\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor
$$
至此，对于左边，可线性预处理 $\mu(n)$ 的前缀和，对于右边，数论分块即可。时间复杂度为 $O(n+T\sqrt{n})$

代码实现

int n, p[MAXN], cnt, m, d, T; ll mu[MAXN] = {0, 1}; bool v[MAXN];
for (int i = 2; i <= MAXN - 5; i++) {
    if (!v[i]) p[++cnt] = i, mu[i] = - 1;
    for (int j = 1; j <= cnt && p[j] * i <= MAXN - 5; j++) {
        v[i * p[j]] = 1;
        if (i % p[j] == 0) break;
        mu[i * p[j]] = -mu[i];
    } } for (int i = 1; i <= n; i++) mu[i] += mu[i - 1];
scanf("%d", &T);
while (T--) {
    scanf("%d%d%d", &m, &n, &d); 
    if (m > n) std::swap(m, n); ll sum = 0;
    for (int x = 1, gx; x <= m; x = gx + 1) {
        gx = std::min(m / (m / x), n / (n / x));
        sum += (mu[gx] - mu[x - 1]) * (m / x / d) * (n / x / d);
    } printf("%lld\n", sum);
}

II

多组询问，求
$$
\sum_{i=1}^n\sum_{j=1}^m\text{gcd}(i,j)
$$
其中 $T \le 10^4, n,m \le 10^7$
由 $I=\varphi \ast 1$，得
$$
= \sum_{i=1}^n\sum_{j=1}^m\sum_{d|\text{gcd}(i,j)}\varphi(d)
$$
同 I，最后可得
$$
=\sum_{d=1}^n\varphi(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor
$$
做法和时间复杂度同 I

III

多组询问，求
$$
\sum_{i=1}^n\sum_{j=1}^m[\text{gcd}(i,j)=d]
$$
其中 $T \le 10^4, n,m,d \le 10^7$
考虑将 $d$ 变为 $1$ 后再进行转化。由最大公约数的定义可知 $\text{gcd}(\dfrac{i}{d},\dfrac{j}{d})=1$，也就相当于 $i,j$ 枚举的上界发生了变化，可得
$$
=\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[\text{gcd}(i,j)=1]
$$
同 I，最后亦可得
$$
=\sum_{x=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(x)\left\lfloor\dfrac{n}{xd}\right\rfloor\left\lfloor\dfrac{m}{xd}\right\rfloor
$$
做法和时间复杂度同 I

IV

多组询问，求
$$
\sum_{i=1}^n\sum_{j=1}^m\text{lcm}(i,j)
$$
其中 $T \le 10^4, n,m \le 10^7$
由小学学过的 $(a, b)\times[a,b]=a\times b$ 可知
$$
=\sum_{i=1}^n\sum_{j=1}^m\dfrac{ij}{\text{gcd}(i,j)}
$$
设 $d=\text{gcd}(i,j),i=i’d, j=j’d$，显然有 $\text{gcd}(i’,j’)=1$，则
$$
=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,d|j,\text{gcd}(i’,j’)=1}\dfrac{ij}{d}
$$

$$
=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,d|j,\text{gcd}(i’,j’)=1}i’j’d
$$
同 I，改变枚举顺序，先枚举 $d$，则有（为书写美观，记 $i=i’,j=j’$）
$$
=\sum_{d=1}^nd\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\text{gcd}(i,j)=1]ij
$$
同理
$$
=\sum_{d=1}^nd\sum_{x=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(x)\sum_{x|i}\sum_{x|j}ij
$$
再设 $i=i’’x,j=j’’x$，则有
$$
=\sum_{d=1}^nd\sum_{x=1}^{\left\lfloor\frac{n}{d}\right\rfloor}x^2\mu(x)\sum_{i’’=1}^{\left\lfloor\frac{n}{xd}\right\rfloor}\sum_{j’’=1}^{\left\lfloor\frac{m}{xd}\right\rfloor}i’’j’’
$$
不妨设 $f(n)=\sum\limits_{i=1}^ni=\dfrac{n(n+1)}{2}$，则有
$$
=\sum_{d=1}^nd\sum_{x=1}^{\left\lfloor\frac{n}{d}\right\rfloor}x^2\mu(x)f(\left\lfloor\dfrac{n}{xd}\right\rfloor)f(\left\lfloor\frac{m}{xd}\right\rfloor)
$$
至此，可以线性预处理 $f(n)$ 和 $g(n)=\sum\limits_{i=1}^{n}i^2\mu(i)$ 的前缀和。再通过数论分块即可解决。时间复杂度同 I。

代码实现

int n, m, cnt, ans;
int f[MAXN], p[MAXN], sum[MAXN];
bool v[MAXN];
scanf("%d%d", &n, &m); f[1] = 1;
if (n < m) swap(n, m);
for (int i = 2; i <= n; i++) {
    if (!v[i]) v[i] = 1 , f[i] = (1 - i + MOD) % MOD, p[++cnt] = i;
    for (int j = 1; j <= cnt && p[j] * i <= n; j++) {
        v[i * p[j]] = 1;
        if (i % p[j]) f[i * p[j]] = 1ll * f[i] * f[p[j]] % MOD;
        else {f[i * p[j]] = f[i]; break;}
    } } for (int i = 1; i <= n; i++)
    f[i] = (f[i - 1] + 1ll * i * f[i] % MOD) %MOD, sum[i] = (1ll * sum[i - 1] + i) % MOD;
for (int x = 1, gx; x <= m; x = gx + 1) {
    gx = min(m / (m / x), n / (n / x));
    ans = (ans + 1ll * (f[gx] - f[x - 1] + MOD) % MOD * sum[n / x] % MOD * sum[m / x] % MOD) % MOD;
} printf("%d", ans);

例题

LG2257

多组数据，求
$$
\sum_{p\in\text{prime}}\sum_{i=1}^n\sum_{j=1}^m[\text{gcd}(i,j)=p]
$$
其中 $T \le 10^4, n,m \le 10^7$。
由应用 III 可得
$$
=\sum_{p\in\text{prime}}\sum_{x=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\mu(x)\left\lfloor\dfrac{n}{xp}\right\rfloor\left\lfloor\dfrac{m}{xp}\right\rfloor
$$
设 $T = xp$，可得 $p|T$，改变枚举顺序，先枚举 $T$，可得
$$
=\sum_{T=1}^n\sum_{p|T, p \in \text{prime}}\mu(\dfrac{T}{P})\left\lfloor\dfrac{n}{T}\right\rfloor\left\lfloor\dfrac{m}{T}\right\rfloor
$$

$$
=\sum_{T=1}^n \left\lfloor\dfrac{n}{T}\right\rfloor\left\lfloor\dfrac{m}{T}\right\rfloor\sum_{p|T, p \in prime}\mu(\dfrac{T}{P})
$$
至此，右边可以枚举质数的倍数，左边数论分块即可。时间复杂度为 $ O(n + \pi(n)\ln n + T\sqrt{n})$。

代码实现

int p[MAXN], mu[MAXN] = {0, 1}, cnt, f[MAXN];
bool v[MAXN];
for (int i = 2; i <= MAXN - 5; i++) {
    if (!v[i]) mu[i] = -1, p[++cnt] = i;
    for (int j = 1; j <= cnt && i * p[j] <= MAXN - 5; j++) {
        v[i * p[j]] = 1;
        if (i % p[j]) mu[i * p[j]] = -mu[i];
        else break;
    } }for (int i = 1; i <= cnt; i++)
    for (int j = 1; j * p[i] <= MAXN - 5; j++) f[j * p[i]] += mu[j];
for (int i = 1; i <= MAXN - 5; i++) f[i]+= f[i - 1];
int T = read(); 
while (T--) {
    int n = read(), m = read(); ll ans = 0;
    if (n > m) n ^= m ^= n ^= m;
    for (int i = 1, gx; i <= n; i = gx + 1) {
        gx = min(n / (n / i), m / (m / i));
        ans += 1ll * (f[gx] - f[i - 1]) * (n / i) * (m / i);
    } write(ans);
}

CF1139D

对一个数列不断添加 $[1,n]$ 的数，直到数列中所有数的 $\text{gcd}=1$ 为止，求期望长度。$n \le 10^5$。

考虑 $\text{dp}$，设 $f_i$ 为当前数列 $\text{gcd}=i$ 时变为 $\text{gcd}=1$ 所用的期望次数。显然 $f_1=0$。则答案
$$
ans=\dfrac{1}{n}\sum_{i=1}^nf_i+1
$$
其中 $1$ 为第一个数就为 $1$ 的情况，然后枚举 $[2,n]$ 的数，每一个数都有 $\dfrac{1}{n}$ 的概率选到。
考虑状态转移方程
$$
f_i=\dfrac{1}{n}\sum_{j=1}^{n}f_{\text{gcd}(i,j)}+1
$$
其中 $1$ 表示转移时的贡献，再枚举下一个数，则所对应的状态为 $f_{\text{gcd}(d,i)}$，而每一个数都有 $\dfrac{1}{n}$ 的概率选到。
考虑莫比乌斯反演，先枚举 $d=\text{gcd}(i, j)$，化分母得
$$
nf_i=\sum_{d|i}f_d\sum_{j=1}^{n}[\text{gcd}(i,j)=d]+n
$$
由应用 III，
$$
nf_i=\sum_{d|i}f_d\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\text{gcd}(\dfrac{i}{d},j)=1]+n
$$

$$
nf_i=\sum_{d|i}f_d\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{x|\text{gcd}(\frac{i}{d},j)}\mu(x)+n
$$

$$
nf_i=\sum_{d|i}f_d\sum_{x=1}^n\mu(x)\left\lfloor\dfrac{n}{xd}\right\rfloor+n
$$
设 $T=xd$，改变枚举顺序，先枚举 $T$ 得
$$
nf_i=\sum_{T|i}\left\lfloor\dfrac{n}{T}\right\rfloor\sum_{d|T}f_d\mu(\dfrac{T}{d})+n
$$
特别的，当 $T=d=i$ 时，等式右边含有未知量，考虑将其移至左边
$$
nf_i=\sum_{T|i}\left\lfloor\dfrac{n}{T}\right\rfloor\sum_{d|T,d\not=i}f_d\mu(\dfrac{T}{d})+n + \mu(1)f_i\left\lfloor\dfrac{n}{i}\right\rfloor
$$

$$
(n-\left\lfloor\dfrac{n}{i}\right\rfloor)f_i=\sum_{T|i}\left\lfloor\dfrac{n}{T}\right\rfloor\sum_{d|T,d\not=i}\mu(\dfrac{T}{d})f_d+n
$$
至此，可以预处理每一个数的因子和 $\mu(n)$ 的前缀和，递推即可。此外，由于涉及到除法运算，要线性预处理逆元。时间复杂度为 $O(n\log^2n)$

代码实现

int n, v[MAXN], p[MAXN], mu[MAXN], m, inv[MAXN], f[MAXN], ans;
std::vector<int> a[MAXN];
scanf("%d", &n); mu[1] = inv[1] = 1;
for (int i = 2; i <= n; i++) {
    if (!v[i]) p[++m] = i, mu[i] = -1;
    for (int j = 1; j <= m && i * p[j] <= n; j++) {
        v[i * p[j]] = 1;
        if (i % p[j]) mu[i * p[j]] = -mu[i];
        else break;
    } } for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i) a[j].push_back(i);
for (int i = 2; i <= n; i++) inv[i] = 1ll* (P - P / i) * inv[P % i] % P;
for (int i = 2; i <= n; i++) {
    f[i] = n;
    for (size_t j = 0, sz = a[i].size(); j < sz; j++) {
        int T = a[i][j], res1 = 0;
        for (int k = 0, sz1 = a[T].size(); k < sz1; k++)
            if (a[T][k] != i)
                res1 = (1ll * res1 + mu[T / a[T][k]] * f[a[T][k]] + P) % P;
        f[i] = (f[i] + 1ll * res1 * (n / T) % P) % P;
    } f[i] = 1ll * f[i] * inv[n - n / i] % P;
    ans = (ans + f[i]) % P;
} printf("%lld", 1ll * ans * inv[n] % P +1);

Another Solution

$$
\begin{aligned}
E(X)&=\sum_{i\ge 1}P(X=i)i\
&=\sum_{i\ge 1}P(X=1)\sum_{j=1}^i1\
&=\sum_{j\ge 1}\sum_{i\ge j}P(X=i)\
&=\sum_{i\ge 1}P(X\ge i)\
&=1-\sum_{i\ge 1}P(X>i)
\end{aligned}
$$
$$
\begin{aligned}
P(X>1)&=1-P(X=1)\
&=1-\dfrac{[\sum\cdots\sum gcd=1]}{m^i}
&=1-\dfrac{\sum\mu(d)\left\lfloor\frac md\right\rfloor^i}{m^i}
\end{aligned}
$$

LG4449

求
$$
\sum_{i=1}^n\sum_{j=1}^m\text{gcd}(i,j)^k
$$
其中 $T \le 10^3, n,m,k \le 10^6$

设 $id_k = f(n) \ast 1$，则 $f(n) = id_k \ast \mu$，得到
$$
=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|\text{gcd}(i,j)}f(d)
$$
由应用 I，得
$$
=\sum_{d=1}^nf(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor
$$

$$
=\sum_{d=1}^n\sum_{x|d}x^k\mu(\dfrac{d}{x})\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor
$$

$$
=\sum_{d=1}^n\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor\sum_{x|d}x^k\mu(\dfrac{d}{x})
$$
至此，由于右半部分相当于 $f(d)$，是一个积性函数，可以在线性时间内求值并算出前缀和。左半部分可以用数论分块求得。时间复杂度为 $O((n + T\sqrt{n})\log k)$。
$$
f(x)=\begin{cases}1&x=1\\p^k-1&p\in\text{prime}\end{cases}
$$

$$
f(xp)=\begin{cases}f(x)f(p)&\text{gcd}(x,p)=1\\p^kf(x)&\text{gcd}(x,p)\not=1\end{cases}\quad p\in\text{prime}
$$

代码实现

int k, T, v[MAXN], p[MAXN], m; ll f[MAXN];
read(T, k); f[1] = 1;
for (int i = 2; i <= MAXN - 5; i++) {
    if (!v[i]) p[++m] = i, f[i] = (fpow(i, k) - 1 + MOD) % MOD;
    for (int j = 1; j <= m && p[j] * i <= MAXN - 5; j++) {
        v[i * p[j]] = 1;
        if (i % p[j] == 0) {
            f[i * p[j]] = f[i] * (f[p[j]] + 1) % MOD;
            break;
        } f[i * p[j]] = f[i] * f[p[j]] % MOD;
    } } for (int i = 2; i <= MAXN - 5; i++) f[i] = (f[i - 1] + f[i]) % MOD;
while (T--) {
    int x, y; read(x, y); ll ans = 0;
    if (x > y) swap(x, y);
    for (int i = 1, gx; i <= x; i = gx + 1) {
        gx = min(x / (x / i), y / (y / i));
        ans = (ans + (f[gx] - f[i - 1] + MOD) % MOD * (x / i) % MOD * (y / i) % MOD) % MOD;
    } write(ans);
}