学习笔记《莫比乌斯反演》

$\mu$ 的定义，性质，和几道例题。

定义

$$\mu(d) = \begin{cases} 1&n=1\\ (-1)^k&n=\prod_{i=1}^k p_i\\ 0&\text{otherwise} \end{cases}$$

线性求值

1
2
3
4
5
6
7
8
9
10
11
12

void sieve_mu(int n){
    mu[1] = 1;
    FL(i, 2, n){
        if(!vis[i])pri[++len] = i, mu[i] = -1;
        for(int j = 1;j <= len && pri[j] * i <= n; j++){
            vis[pri[j] * i] = 1;
            if(i % pri[j] == 0)break;
            mu[pri[j] * i] = -mu[i];
        }
    }
    FL(i, 1, n)mu[i] = mu[i - 1];
}

性质

$$\sum_{d|n}\mu(d)=[n=1]\\ [gcd(i,j)=1]=\sum_{d|\gcd(i,j)}\mu(d)\\ f(n)=\sum_{d\mid n}g(n)\Rightarrow g(n) = \sum_{d\mid n}f(d)\mu(\frac nd)\\ f(n)=\sum_{n\mid d}g(d)\Rightarrow g(n) = \sum_{n\mid d}f(d)\mu(\frac dn)$$

从这里开始，默认 $n\le m$。

Ex.1

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

$$\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]\\ =&\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid \gcd(i, j)}\mu(d)\\ =&\sum_{d=1}^n \mu(d)\left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor \end{aligned}$$

$\mu(d)$ 前缀和优化，后面的整除分块即可。

如果是求 $\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]$

这也很简单，我们把式子同时除以 $k$，得 $\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]$

然后就一样了。

Ex.2

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

我们假设 $n \le m$，然后枚举 $k \in prime$，得

$$\sum_{i=1}^nk\sum_{i=1}^n\sum_{j=1}^m[\gcd(i, j)=k]=\sum_{k=1}^n\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i, j)=1]\\$$

我们枚举一下 $d = \gcd$，并提到前面。

$$=\sum_{k=1}^n\sum_{i=1}^{\lfloor\frac nk\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d\mid \gcd(i, j)}\mu(d)=\sum_{k=1}^n \sum_{d=1}^{\lfloor\frac nk\rfloor}\mu(d)\left\lfloor\frac n{dk}\right\rfloor\left\lfloor\frac m{dk}\right\rfloor\\$$

由于 $n\le 10^7$，枚举 $k$ 太慢了，我们还要优化，设 $T = dk$

$$= \sum_{k=1}^n\sum_{d=1}^{\lfloor\frac nk\rfloor}\mu(d)\left\lfloor\frac nT\right\rfloor\left\lfloor\frac mT\right\rfloor=\sum_{T=1}^n\left\lfloor\frac nT\right\rfloor\left\lfloor\frac mT\right\rfloor\sum_{k\mid T}\mu(\frac Tk)$$

因为 $id\ast\mu=\varphi$ 所以 $\sum\limits_{k\mid T}\mu(\frac Tk)=\varphi(T)$，最终复杂度 $O(n + \sqrt{n})$。

Ex.3

设 $d(x)$ 为 $x$ 的约数个数，求 $\sum_{i=1}^n\sum_{j=1}^m d(ij)$。

有个结论 $d(ij) = \sum_{x\mid i}\sum_{y\mid j}[\gcd(x, y) = 1]$

我们一个质数$p$，$i=i'*p^{k_1},j=j'*p^{k_2}$。

考虑 $p$ 对 $d(ij)$ 的贡献，显然在 $d$ 的因子中，$p$ 可以为 $0$~$k_1+k_2$ 任意一个。

我们只看 $p$ 这一项，设 $x=x'p^{k_x},y=y'p^{k_y}$

要满足 $\gcd(x,y)=1$，那么就有 $\gcd(p^{k_x},p^{k_y})=1$

要么$k_x=0,k_y\in[0,k_2]$，共$k_2+1$种

要么$k_y=0,k_x\in[0,k_1]$，共$k_1+1$种

减去重复判断的$k_x=0,k_y=0$这种情况，最后答案$k_1+k_2+1$种

我们带入原式得：

$$\begin{aligned} &=\sum_{i=1}^n\sum_{j=1}^m\sum_{x\mid i}\sum_{y \mid j}[gcd(x,y)=1]\\ &=\sum_{i=1}^n\sum_{j=1}^m\sum_{x=1}^n\sum_{y=1}^m\sum_{d\mid gcd(x, y)}[x\mid i][y\mid j]\mu(d)\\ &=\sum_{x=1}^n\sum_{y=1}^m\sum_{d\mid gcd(x, y)}\mu(d)\sum_{i=1}^n[x\mid i]\sum_{j=1}^m[y\mid j]\\ &=\sum_{x=1}^n\sum_{y=1}^m\sum_{d\mid gcd(x, y)}\mu(d)\lfloor\frac nx\rfloor\lfloor\frac my\rfloor\\ &=\sum_{d=1}^n\mu(d)\sum_{x=1}^{\lfloor\frac nd\rfloor}\left\lfloor\frac n{dx}\right\rfloor\sum_{y=1}^{\lfloor\frac md\rfloor}\left\lfloor\frac m{dy}\right\rfloor \end{aligned}$$

Ex.4

求 $\sum_{i=1}^{n}\sum_{j=1}^{m}ij[gcd(i,j)=k]$。

先同时除以$k$，但我们还要考虑 $i,j$ 的变化，除 $k$ 后 $i, j$ 会变为原来的 $\dfrac 1k$，所以最后要乘上 $k^2$。

$$\begin{aligned} &=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij[gcd(i,j)=1]k^2\\ &=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij\sum_{d\mid \gcd(i,j)}\mu(d)k^2\\ &=k^2\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{\lfloor\frac n{kd}\rfloor}i\sum_{j=1}^{\lfloor\frac m{kd}\rfloor}j \end{aligned}$$

最后那两项为等差数列，计算时整除分块，最终复杂度 $O(\sqrt{n})$

Ex.5

求 $\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j)$。
我们知道 $\sum_{d \mid n}\varphi(d) = n$，所以只要把 $\mu$ 换成 $\varphi$，然后正常做即可。

$$\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)&=\sum_{i=1}^n\sum_{j=1}^nij\sum_{d\mid \gcd(i,j)}\varphi(d)\\ &=\sum_{d=1}^n\varphi(d)\sum_{i=1}^n[d\mid i]i\sum_{j=1}^n[d\mid j]j\\ &=\sum_{d=1}^n\varphi(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}xd\sum_{y=1}^{\lfloor\frac{n}{d}\rfloor}yd\\ &=\sum_{d=1}^n\varphi(d)d^2\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}x\sum_{y=1}^{\lfloor\frac{n}{d}\rfloor}y\\ \end{aligned}$$