本文的重点不是处理式子，只是希望带给你一种莫反的新理解。
问题 像各种反演模型一样，莫比乌斯反演是一种代替容斥的强大工具。
它解决的问题如下：如果已知
f k = ∑ d ∣ k g d f_k = \sum_{d | k}g_d f k = ∑ d ∣ k g d ，那么
g k = ∑ d ∣ k f ( k d ) μ ( d ) g_k = \sum_{d | k}f({k \over d})\mu(d) g k = ∑ d ∣ k f ( d k ) μ ( d ) 。
莫比乌斯函数是容斥系数 正整数是一个以质数为基底的高维空间。对于
n = ∏ p i α i n = \prod p_i^{\alpha_i} n = ∏ p i α i ，我们认为它的坐标是
( α 1 , α 2 , ⋯ , α i , ⋯ ) (\alpha_1, \alpha_2, \cdots, \alpha_i, \cdots) ( α 1 , α 2 , ⋯ , α i , ⋯ ) 。可以发现，上述
f k f_k f k 的定义就是此意义下的高维前缀和，现在，我们想根据高维前缀和求出原数组。
类比二维的情况，
a i , j = s u m i , j − s u m i − 1 , j − s u m i , j − 1 + s u m i − 1 , j − 1 a_{i, j} = sum_{i, j} - sum_{i - 1, j} - sum_{i, j - 1} + sum_{i - 1, j - 1} a i , j = s u m i , j − s u m i − 1 , j − s u m i , j − 1 + s u m i − 1 , j − 1 ，稍微手玩一下三维的，我们发现对于维度是
n n n 的情况来说，
g ( α 1 , α 2 , ⋯ , α n ) = ∑ S ⊂ { 1 , 2 , ⋯ , n } ( − 1 ) ∣ S ∣ f ( α 1 − [ 1 ∈ S ] , ⋯ , α i − [ i ∈ S ] , ⋯ , α n − [ n ∈ S ] ) 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 ( α 1 , α 2 , ⋯ , α n ) = ∑ S ⊂ { 1 , 2 , ⋯ , n } ( − 1 ) ∣ S ∣ f ( α 1 − [ 1 ∈ S ] , ⋯ , α i − [ i ∈ S ] , ⋯ , α n − [ n ∈ S ]) 。证明由容斥原理易得。
转化成整除式的表达，
g k = ∑ d ∣ k f ( k d ) μ ( d ) g_k = \sum_{d | k}f({k \over d})\mu(d) g k = ∑ d ∣ k f ( d k ) μ ( d ) ，这个
d d d 就类比上面的
S S S ，也就是挑一些维度减去 1。也就是说，如果
d d d 有
t t t 个本质不同的质因子，那么这个就是容斥系数
( − 1 ) t (-1)^t ( − 1 ) t 。但到这就完了吗？如果
∃ p , p 2 ∣ d \exists p, p^2 | d ∃ p , p 2 ∣ d 那也就意味着，我们至少挑了一些维度把这一维的坐标减去了 2，根据上面的式子，减 2 对于最终答案是没有任何贡献的。因此这种
d d d 的系数就应该是
0 0 0 。
整理一下：
0,& \exists p^2 | d(p > 1) \\
(-1)^k, & d \text{ is a product of
} k \text{ distinct primes}
\end{cases}
这就是莫比乌斯函数的定义了。
一些性质
莫比乌斯函数是积性函数
容易验证。
∑ d ∣ n μ ( d ) = [ n = 1 ] \sum_{d | n} \mu(d) = [n = 1] ∑ d ∣ n μ ( d ) = [ n = 1 ]
n = ∏ i = 1 k p i α i n = \prod_{i = 1}^k p_i^{\alpha_i} n = ∏ i = 1 k p i α i ，
n ′ = ∏ i = 1 k p i n' = \prod_{i = 1}^k p_i n ′ = ∏ i = 1 k p i 。
那么
∑ d ∣ n μ ( d ) = ∑ d ∣ n ′ μ ( d ) = ∑ i = 0 k ( k i ) ( − 1 ) i = [ k = 0 ] \sum_{d|n} \mu(d) = \sum_{d | n'} \mu(d) = \sum_{i = 0}^k {k \choose i}(-1)^i = [k = 0] ∑ d ∣ n μ ( d ) = ∑ d ∣ n ′ μ ( d ) = ∑ i = 0 k ( i k ) ( − 1 ) i = [ k = 0 ] 。
这条性质的本质是由于莫比乌斯函数是上面提到的容斥系数决定的（你会发现这个推导过程跟证明容斥/凑容斥的过程很类似）。
2 性质有一个重要的应用，即
[ gcd ( i , j ) = 1 ] = ∑ d [ d ∣ i ] [ d ∣ j ] μ ( d ) [\gcd(i, j) = 1] = \sum_d [d | i][d | j] \mu(d) [ g cd( i , j ) = 1 ] = ∑ d [ d ∣ i ] [ d ∣ j ] μ ( d ) 这个在推式子时很常用。
同时，2 性质用 Dirichlet 的语言可以描述为
ε = 1 ∗ μ \varepsilon = 1 * \mu ε = 1 ∗ μ 。(
ε ( n ) = [ n = 1 ] \varepsilon(n) = [n = 1] ε ( n ) = [ n = 1 ] ，有性质
∀ f , f ∗ ε = f \forall f, f * \varepsilon = f ∀ f , f ∗ ε = f )
莫比乌斯反演的倍数拓展形式 刚刚提到的形式是针对高维前缀和的，实际上把刚刚的过程全部改成高维后缀和也是没有问题的（甚至可以变成前缀积）。
即
f d = ∑ d ∣ k g k ⟺ g d = ∑ d ∣ k f k μ ( k d ) f_d = \sum_{d | k} g_k \iff g_d = \sum_{d | k} f_k \mu({k \over d}) f d = ∑ d ∣ k g k ⟺ g d = ∑ d ∣ k f k μ ( d k ) 。
从这个角度理解 oi-wiki 上的各种拓展形式或许就自然了许多。
一道例题 莫比乌斯反演的题大部分都是推式子，给一道感受一下吧。
: 求
∑ i = 1 n ∑ j = 1 m lcm ( i , j ) \sum_{i = 1}^n\sum_{j = 1}^m \operatorname{lcm}(i, j) ∑ i = 1 n ∑ j = 1 m lcm ( i , j ) 。
首先，我们擅长的是处理
gcd \gcd g cd。
那么把原式变成:
∑ i = 1 n ∑ j = 1 m i × j gcd ( i , j ) = ∑ k = 1 n 1 k ∑ i = 1 n ∑ j = 1 m [ gcd ( i , j ) = k ] ( i × j ) = ∑ k = 1 n 1 k ∑ i = 1 n ∑ j = 1 m [ k ∣ i ] [ k ∣ j ] [ gcd ( i k , j k ) = 1 ] ( i × j ) = ∑ k = 1 n 1 k ∑ i ′ = 1 ⌊ n k ⌋ ∑ j ′ = 1 ⌊ m k ⌋ [ gcd ( i ′ , j ′ ) = 1 ] ( i ′ k × j ′ k ) = ∑ k = 1 n k ∑ i ′ = 1 ⌊ n k ⌋ i ′ ∑ j ′ = 1 ⌊ m k ⌋ j ′ [ gcd ( i ′ , j ′ ) = 1 ] = ∑ k = 1 n k ∑ i ′ = 1 ⌊ n k ⌋ i ′ ∑ j ′ = 1 ⌊ m k ⌋ j ′ ∑ d [ d ∣ i ′ ] [ d ∣ j ′ ] μ ( d ) = ∑ k = 1 n k ∑ d μ ( d ) ∑ i ′ = 1 ⌊ n k ⌋ [ d ∣ i ′ ] i ′ ∑ j ′ = 1 ⌊ m k ⌋ [ d ∣ j ′ ] j ′ \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} i = 1 ∑ n j = 1 ∑ m g cd( i , j ) i × j = k = 1 ∑ n k 1 i = 1 ∑ n j = 1 ∑ m [ g cd( i , j ) = k ] ( i × j ) = k = 1 ∑ n k 1 i = 1 ∑ n j = 1 ∑ m [ k ∣ i ] [ k ∣ j ] [ g cd( k i , k j ) = 1 ] ( i × j ) = k = 1 ∑ n k 1 i ′ = 1 ∑ ⌊ k n ⌋ j ′ = 1 ∑ ⌊ k m ⌋ [ g cd( i ′ , j ′ ) = 1 ] ( i ′ k × j ′ k ) = k = 1 ∑ n k i ′ = 1 ∑ ⌊ k n ⌋ i ′ j ′ = 1 ∑ ⌊ k m ⌋ j ′ [ g cd( i ′ , j ′ ) = 1 ] = k = 1 ∑ n k i ′ = 1 ∑ ⌊ k n ⌋ i ′ j ′ = 1 ∑ ⌊ k m ⌋ j ′ d ∑ [ d ∣ i ′ ] [ d ∣ j ′ ] μ ( d ) = k = 1 ∑ n k d ∑ μ ( d ) i ′ = 1 ∑ ⌊ k n ⌋ [ d ∣ i ′ ] i ′ j ′ = 1 ∑ ⌊ k m ⌋ [ d ∣ j ′ ] j ′ 记
G ( x ) = ∑ i = 1 x [ d ∣ i ] i G(x) = \sum_{i = 1}^x[d | i]i G ( x ) = ∑ i = 1 x [ d ∣ i ] i ，实际上是一个等差数列求和，
G ( x ) = 1 2 ( d + d × ⌊ x d ⌋ ) ⌊ x d ⌋ = d × 1 2 × ( 1 + ⌊ x d ⌋ ) ⌊ x d ⌋ : = d × g ( ⌊ x d ⌋ ) 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) G ( x ) = 2 1 ( d + d × ⌊ d x ⌋) ⌊ d x ⌋ = d × 2 1 × ( 1 + ⌊ d x ⌋) ⌊ d x ⌋ := d × g (⌊ d x ⌋) 。带回原式，并根据
⌊ ⌊ a b ⌋ c ⌋ = ⌊ a b c ⌋ \lfloor {{\lfloor {a \over b} \rfloor} \over c} \rfloor = \lfloor \frac{a}{bc} \rfloor ⌊ c ⌊ b a ⌋ ⌋ = ⌊ b c a ⌋ 得到：
∑ k = 1 n k ∑ d μ ( d ) d 2 g ( ⌊ n k d ⌋ ) g ( ⌊ m k d ⌋ ) \sum_{k = 1}^n k \sum_d \mu(d)d^2 g(\lfloor \frac{n}{kd} \rfloor) g(\lfloor \frac{m}{kd} \rfloor) ∑ k = 1 n k ∑ d μ ( d ) d 2 g (⌊ k d n ⌋) g (⌊ k d m ⌋)
根据 oi-wiki 的技巧，此时经常用
l = k × d l = k \times d l = k × d 进行替换，即：
∑ l = 1 n l g ( ⌊ n l ⌋ ) g ( ⌊ m l ⌋ ) ∑ d ∣ l μ ( d ) d \sum_{l = 1}^n l g(\lfloor \frac{n}{l} \rfloor) g(\lfloor \frac{m}{l} \rfloor) \sum_{d | l} \mu(d)d ∑ l = 1 n l g (⌊ l n ⌋) g (⌊ l m ⌋) ∑ d ∣ l μ ( d ) d 记录
f ( l ) = ∑ d ∣ l μ ( d ) d f(l) = \sum_{d | l} \mu(d)d f ( l ) = ∑ d ∣ l μ ( d ) d ，首先
h ( d ) = μ ( d ) d h(d) = \mu(d)d h ( d ) = μ ( d ) d 是积性函数（积性函数的积还是积性函数），那么
f = h ∗ 1 f = h * 1 f = h ∗ 1 也是积性函数。那么我们线性筛
f f f 即可。最后遍历一遍
l l l 求出答案。
CPP #include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7 + 5 , mod = 20101009 , i2 = 10050505 ;
bitset<N> vis;
int pri[N], cnt, g[N], f[N];
int G (int x) return x * (x + 1 ) % mod * i2 % mod;
}
signed main () 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 <= n; ++i){
if (!vis[i]){
pri[++cnt] = i;
f[i] = 1 - i;
g[i] = i;
}
for (int j = 1 ; j <= cnt; ++j){
if (i * pri[j] > n) break ;
int nxt = i * pri[j];
vis[nxt] = 1 ;
if (i % pri[j] == 0 ){
g[nxt] = g[i] * pri[j];
f[nxt] = (f[nxt / g[nxt]] * f[pri[j]]) % mod;
break ;
}
g[nxt] = pri[j];
f[nxt] = (f[nxt / pri[j]] * f[pri[j]]) % mod;
}
}
int ans = 0 ;
for (int l = 1 ; l <= n; ++l){
(ans += G (n / l) * G (m / l) % mod * l % mod * f[l] % mod) %= mod;
}
cout << (ans % mod + mod) % mod;
return 0 ;
}
P1829