莫比乌斯反演

只做了一两道，浅写一点。
问题

像各种反演模型一样，莫比乌斯反演是一种代替容斥的强大工具。
它解决的问题如下：如果已知 \(f_k = \sum_{d | k}g_d\)，那么 \(g_k = \sum_{d | k}f({k \over d})\mu(d)\)。
莫比乌斯函数是容斥系数

正整数是一个以质数为基底的高维空间。对于 \(n = \prod p_i^{\alpha_i}\)，我们认为它的坐标是 \((\alpha_1, \alpha_2, \cdots, \alpha_i, \cdots)\)。可以发现，上述 \(f_k\) 的定义就是此意义下的高维前缀和，现在，我们想根据高维前缀和求出原数组。
类比二维的情况，\(a_{i, j} = sum_{i, j} - sum_{i - 1, j} - sum_{i, j - 1} + sum_{i - 1, j - 1}\)，稍微手玩一下三维的，我们发现对于维度是 \(n\) 的情况来说， \(g_{(\alpha_1, \alpha_2, \cdots, \alpha_n)} = \sum_{S \subset \{1, 2, \cdots, n \} } (-1)^{|S|} f_{(\alpha_1 - [1 \in S], \cdots, \alpha_{i} - [i \in S], \cdots, \alpha_n - [n \in S])}\) 由容斥原理易得。
转化成整除式的表达，\(g_k = \sum_{d | k}f({k \over d})\mu(d)\)，这个 \(d\) 就类比上面的 \(S\)，也就是挑一些维度减去 1。也就是说，如果 \(d\) 有 \(t\) 个本质不同的质因子，那么这个就是容斥系数 \((-1)^t\)。但到这就完了吗？如果 \(\exists p, p^2 | d\) 那也就意味着，我们至少挑了一些维度把这一维的坐标减去了 2，根据上面的式子，减 2 对于最终答案是没有任何贡献的。因此这种 \(d\) 的系数就应该是 \(0\)。
整理一下：

\[ \mu(d) \begin{cases} 1,& d = 1 \\0,& \exists p^2 | d(p > 1) \\(-1)^k, & d \text{ is a product of} k \text{ distinct primes}\end{cases}\]
这就是莫比乌斯函数的定义了。
一些性质

• 莫比乌斯函数是积性函数
  

容易验证。

• \(\sum_{d | n} \mu(d) = [n = 1]\)。
  

\(n = \prod_{i = 1}^k p_i^{\alpha_i}\)，\(n' = \prod_{i = 1}^k p_i\)。
那么 \(\sum_{d|n} \mu(d) = \sum_{d | n'} \mu(d) = \sum_{i = 0}^k {k \choose i}(-1)^i = [k = 0]\)。
这条性质的本质是由于莫比乌斯函数是上面提到的容斥系数决定的（你会发现这个推导过程跟证明容斥/凑容斥的过程很类似）。
2 性质有一个重要的应用，即 \([\gcd(i, j) = 1] = \sum_d [d | i][d | j] \mu(d)\) 这个在推式子时很常用。
同时，2 性质用 Dirichlet 的语言可以描述为 \(\varepsilon = 1 * \mu\)。(\(\varepsilon(n) = [n = 1]\)，有性质 \(\forall f, f * \varepsilon = f\))
莫比乌斯反演的倍数拓展形式

刚刚提到的形式是针对高维前缀和的，实际上把刚刚的过程全部改成高维后缀和也是没有问题的（甚至可以变成前缀积）。
即 \(f_d = \sum_{d | k} g_k \iff g_d = \sum_{d | k} f_k \mu({k \over d})\)。
从这个角度理解 oi-wiki 上的各种拓展形式或许就自然了许多。
一道例题

莫比乌斯反演的题大部分都是推式子，给一道感受一下吧。
P1829: 求 \(\sum_{i = 1}^n\sum_{j = 1}^m \operatorname{lcm}(i, j)\)。
首先，我们擅长的是处理 \(\gcd\)。
那么把原式变成:

\[\begin{aligned}\sum_{i = 1}^n \sum_{j = 1}^m \frac{i \times j}{\gcd(i, j)} &= \sum_{k = 1}^n \frac{1}{k} \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) = k](i \times j) \\&= \sum_{k = 1}^n \frac{1}{k} \sum_{i = 1}^n \sum_{j = 1}^m [k | i][k | j][\gcd({i \over k}, {j \over k}) = 1](i \times j) \\&= \sum_{k = 1}^n \frac{1}{k} \sum_{i' = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j' = 1}^{\lfloor \frac{m}{k} \rfloor} [\gcd(i', j') = 1](i'k \times j'k) \\&= \sum_{k = 1}^n k \sum_{i' = 1}^{\lfloor \frac{n}{k} \rfloor} i' \sum_{j' = 1}^{\lfloor \frac{m}{k} \rfloor} j' [\gcd(i', j') = 1] \\&= \sum_{k = 1}^n k \sum_{i' = 1}^{\lfloor \frac{n}{k} \rfloor} i' \sum_{j' = 1}^{\lfloor \frac{m}{k} \rfloor} j' \sum_d [d | i'][d | j']\mu(d) \\&= \sum_{k = 1}^n k \sum_d \mu(d) \sum_{i' = 1}^{\lfloor \frac{n}{k} \rfloor} [d | i'] i' \sum_{j' = 1}^{\lfloor \frac{m}{k} \rfloor} [d | j']j' \end{aligned}\]
记 \(G(x) = \sum_{i = 1}^x[d | i]i\)，实际上是一个等差数列求和，\(G(x) = \frac{1}{2}(d + d \times \lfloor \frac{x}{d} \rfloor)  \lfloor \frac{x}{d} \rfloor = d \times \frac{1}{2} \times (1 + \lfloor \frac{x}{d} \rfloor)  \lfloor \frac{x}{d} \rfloor := d \times g(\lfloor \frac{x}{d} \rfloor)\)。带回原式，并根据 \(\lfloor {{\lfloor {a \over b} \rfloor} \over c} \rfloor = \lfloor \frac{a}{bc} \rfloor\) 得到：

\[\sum_{k = 1}^n k \sum_d \mu(d)d^2 g(\lfloor \frac{n}{kd} \rfloor) g(\lfloor \frac{m}{kd} \rfloor) \]
根据 oi-wiki 的技巧，此时经常用 \(l = k \times d\) 进行替换，即：

\[\sum_{l = 1}^n l g(\lfloor \frac{n}{l} \rfloor) g(\lfloor \frac{m}{l} \rfloor) \sum_{d | l} \mu(d)d  \]
记录 \(f(l) = \sum_{d | l} \mu(d)d\)，首先 \(h(d) = \mu(d)d\) 是积性函数（积性函数的积还是积性函数），那么 \(f = h * 1\) 也是积性函数。那么我们线性筛 \(f\) 即可。最后遍历一遍 \(l\) 求出答案。
复杂度 \(O(n)\)。
Code[code]#include using namespace std;#define int long longconst int N = 1e7 + 5, mod = 20101009, i2 = 10050505;bitset vis;int pri[N], cnt, g[N], f[N];int G(int x){    return x * (x + 1) % mod * i2 % mod;}signed main(){    ios::sync_with_stdio(0);    cin.tie(0), cout.tie(0);    int n, m;    cin >> n >> m;    f[1] = 1;    if(n > m) swap(n, m);    for(int i = 2; i