莫比烏斯反演
引入
莫比烏斯反演是數論中的重要內容。對於一些函數 \(f(n)\) ，如果很難直接求出它的值，而容易求出其倍數和或約數和 \(g(n)\) ，那麼可以通過莫比烏斯反演簡化運算，求得 \(f(n)\) 的值。
開始學習莫比烏斯反演前，需要先學習一些前置知識：數論分塊 、狄利克雷卷積 。
莫比烏斯函數
定義
\(\mu\) 為莫比烏斯函數，定義為
\[
\mu(n)=
\begin{cases}
1&n=1\\
0&n\text{ 含有平方因子}\\
(-1)^k&k\text{ 為 }n\text{ 的本質不同質因子個數}\\
\end{cases}
\]
詳細解釋一下：
令 \(n=\prod_{i=1}^kp_i^{c_i}\) ，其中 \(p_i\) 為質因子，\(c_i\ge 1\) 。上述定義表示：
\(n=1\) 時，\(\mu(n)=1\) ；對於 \(n\not= 1\) 時：
當存在 \(i\in [1,k]\) ，使得 \(c_i > 1\) 時，\(\mu(n)=0\) ，也就是説只要某個質因子出現的次數超過一次，\(\mu(n)\) 就等於 \(0\) ；
當任意 \(i\in[1,k]\) ，都有 \(c_i=1\) 時，\(\mu(n)=(-1)^k\) ，也就是説每個質因子都僅僅只出現過一次時，即 \(n=\prod_{i=1}^kp_i\) ，\(\{p_i\}_{i=1}^k\) 中個元素唯一時，\(\mu(n)\) 等於 \(-1\) 的 \(k\) 次冪，此處 \(k\) 指的便是僅僅只出現過一次的質因子的總個數。
性質
莫比烏斯函數不僅是積性函數，還有如下性質：
\[
\sum_{d\mid n}\mu(d)=
\begin{cases}
1&n=1\\
0&n\neq 1\\
\end{cases}
\]
即 \(\sum_{d\mid n}\mu(d)=\varepsilon(n)\) ，\(\mu * 1 =\varepsilon\)
證明
設 \(\displaystyle n=\prod_{i=1}^k{p_i}^{c_i},n'=\prod_{i=1}^k p_i\)
那麼 \(\displaystyle\sum_{d\mid n}\mu(d)=\sum_{d\mid n'}\mu(d)=\sum_{i=0}^k \dbinom{k}{i}\cdot(-1)^i=(1+(-1))^k\)
根據二項式定理，易知該式子的值在 \(k=0\) 即 \(n=1\) 時值為 \(1\) 否則為 \(0\) ，這也同時證明了 \(\displaystyle\sum_{d\mid n}\mu(d)=[n=1]=\varepsilon(n)\) 以及 \(\mu\ast 1=\varepsilon\)
注
這個性質意味着，莫比烏斯函數在狄利克雷生成函數中，等價於黎曼函數 \(\zeta\) 的倒數。所以在狄利克雷卷積中，莫比烏斯函數是常數函數 \(1\) 的逆元。
補充結論
反演結論：\(\displaystyle [\gcd(i,j)=1]=\sum_{d\mid\gcd(i,j)}\mu(d)\)
直接推導 ：如果看懂了上一個結論，這個結論稍加思考便可以推出：如果 \(\gcd(i,j)=1\) 的話，那麼代表着我們按上個結論中枚舉的那個 \(n\) 是 \(1\) ，也就是式子的值是 \(1\) ，反之，有一個與 \([\gcd(i,j)=1]\) 相同的值：\(0\)
利用 \(\varepsilon\) 函數 ：根據上一結論，\([\gcd(i,j)=1]=\varepsilon(\gcd(i,j))\) ，將 \(\varepsilon\) 展開即可。
線性篩
由於 \(\mu\) 函數為積性函數，因此可以線性篩莫比烏斯函數（線性篩基本可以求所有的積性函數，儘管方法不盡相同）。
線性篩實現
拓展
證明
\[
\varphi \ast 1=\operatorname{id}
\]
將 \(n\) 分解質因數：\(\displaystyle n=\prod_{i=1}^k {p_i}^{c_i}\)
首先，因為 \(\varphi\) 是積性函數，故只要證明當 \(n'=p^c\) 時 \(\displaystyle\varphi \ast 1=\sum_{d\mid n'}\varphi(\frac{n'}{d})=\operatorname{id}\) 成立即可。
因為 \(p\) 是質數，於是 \(d=p^0,p^1,p^2,\cdots,p^c\)
易知如下過程：
\[
\begin{aligned}
\varphi \ast 1&=\sum_{d\mid n}\varphi(\frac{n}{d})\\
&=\sum_{i=0}^c\varphi(p^i)\\
&=1+p^0\cdot(p-1)+p^1\cdot(p-1)+\cdots+p^{c-1}\cdot(p-1)\\
&=p^c\\
&=\operatorname{id}\\
\end{aligned}
\]
該式子兩側同時卷 \(\mu\) 可得 \(\displaystyle\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d})\)
莫比烏斯變換
設 \(f(n),g(n)\) 為兩個數論函數。
形式一：如果有 \(f(n)=\sum_{d\mid n}g(d)\) ，那麼有 \(g(n)=\sum_{d\mid n}\mu(d)f(\frac{n}{d})\) 。
這種形式下，數論函數 \(f(n)\) 稱為數論函數 \(g(n)\) 的莫比烏斯變換，數論函數 \(g(n)\) 稱為數論函數 \(f(n)\) 的莫比烏斯逆變換（反演）。
容易看出，數論函數 \(g(n)\) 的莫比烏斯變換，就是將數論函數 \(g(n)\) 與常數函數 \(1\) 進行狄利克雷卷積。
注
根據狄利克雷卷積與狄利克雷生成函數的對應關係，數論函數 \(g(n)\) 的莫比烏斯變換對應的狄利克雷生成函數，就是數論函數 \(g(n)\) 的狄利克雷生成函數與黎曼函數 \(\zeta\) 的乘積。
形式二：如果有 \(f(n)=\sum_{n|d}g(d)\) ，那麼有 \(g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)\) 。
證明
方法一：對原式做數論變換。
\[
\sum_{d\mid n}\mu(d)f(\frac{n}{d})=\sum_{d\mid n}\mu(d)\sum_{k\mid \frac{n}{d}}g(k)=\sum_{k\mid n}g(k)\sum_{d\mid \frac{n}{k}}\mu(d)=g(n)
\]
用 \(\displaystyle\sum_{d\mid n}g(d)\) 來替換 \(f(\dfrac{n}{d})\) ，再變換求和順序。最後一步變換的依據：\(\displaystyle\sum_{d\mid n}\mu(d)=[n=1]\) ，因此在 \(\dfrac{n}{k}=1\) 時第二個和式的值才為 \(1\) 。此時 \(n=k\) ，故原式等價於 \(\displaystyle\sum_{k\mid n}[n=k]\cdot g(k)=g(n)\)
方法二：運用卷積。
原問題為：已知 \(f=g\ast1\) ，證明 \(g=f\ast\mu\)
易知如下轉化：\(f\ast\mu=g*1*\mu\implies f\ast\mu=g\) （其中 \(1\ast\mu=\varepsilon\) ）。
對於第二種形式：
類似上面的方法一，我們考慮逆推這個式子。
\[
\begin{aligned}
&\sum_{n|d}{\mu(\frac{d}{n})f(d)} \\
=& \sum_{k=1}^{+\infty}{\mu(k)f(kn)}
= \sum_{k=1}^{+\infty}{\mu(k)\sum_{kn|d}{g(d)}} \\
=& \sum_{n|d}{g(d)\sum_{k|\frac{d}{n}}{\mu(k)}}
= \sum_{n|d}{g(d)\epsilon(\frac{d}{n})} \\
=& g(n)
\end{aligned}
\]
我們把 \(d\) 表示為 \(kn\) 的形式，然後把 \(f\) 的原定義代入式子。
發現枚舉 \(k\) 再枚舉 \(kn\) 的倍數可以轉換為直接枚舉 \(n\) 的倍數再求出 \(k\) ，發現後面那一塊其實就是 \(\epsilon\) , 整個式子只有在 \(d=n\) 的時候才能取到值。
問題形式
求值（多組數據）
\[
\sum_{i=x}^{n}\sum_{j=y}^{m}[\gcd(i,j)=k]\qquad (1\leqslant T,x,y,n,m,k\leqslant 5\times 10^4)
\]
根據容斥原理，原式可以分成 \(4\) 塊來處理，每一塊的式子都為
\[
\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k]
\]
考慮化簡該式子
\[
\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]
\]
因為 \(\gcd(i,j)=1\) 時對答案才用貢獻，於是我們可以將其替換為 \(\varepsilon(\gcd(i,j))\) （\(\varepsilon(n)\) 當且僅當 \(n=1\) 時值為 \(1\) 否則為 \(0\) ），故原式化為
\[
\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\varepsilon(\gcd(i,j))
\]
將 \(\varepsilon\) 函數展開得到
\[
\displaystyle\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d\mid \gcd(i,j)}\mu(d)
\]
變換求和順序，先枚舉 \(d\mid \gcd(i,j)\) 可得
\[
\displaystyle\sum_{d=1}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d\mid i]\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d\mid j]
\]
易知 \(1\sim\lfloor\dfrac{n}{k}\rfloor\) 中 \(d\) 的倍數有 \(\lfloor\dfrac{n}{kd}\rfloor\) 個，故原式化為
\[
\displaystyle\sum_{d=1}^{\min(\lfloor \frac{n}{k}\rfloor,\lfloor \frac{m}{k}\rfloor)}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor
\]
很顯然，式子可以數論分塊求解。
時間複雜度 \(\Theta(N+T\sqrt{n})\)
代碼實現
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 #include <algorithm>
#include <cstdio>
using namespace std ;
const int N = 50000 ;
int mu [ N + 5 ], p [ N + 5 ];
bool flg [ N + 5 ];
void init () {
int tot = 0 ;
mu [ 1 ] = 1 ;
for ( int i = 2 ; i <= N ; ++ i ) {
if ( ! flg [ i ]) {
p [ ++ tot ] = i ;
mu [ i ] = -1 ;
}
for ( int j = 1 ; j <= tot && i * p [ j ] <= N ; ++ j ) {
flg [ i * p [ j ]] = 1 ;
if ( i % p [ j ] == 0 ) {
mu [ i * p [ j ]] = 0 ;
break ;
}
mu [ i * p [ j ]] = - mu [ i ];
}
}
for ( int i = 1 ; i <= N ; ++ i ) mu [ i ] += mu [ i - 1 ];
}
int solve ( int n , int m ) {
int res = 0 ;
for ( int i = 1 , j ; i <= min ( n , m ); i = j + 1 ) {
j = min ( n / ( n / i ), m / ( m / i ));
res += ( mu [ j ] - mu [ i - 1 ]) * ( n / i ) * ( m / i ); // 代推出来的式子
}
return res ;
}
int main () {
int T , a , b , c , d , k ;
init (); // 预处理mu数组
scanf ( "%d" , & T );
for ( int i = 1 ; i <= T ; i ++ ) {
scanf ( "%d%d%d%d%d" , & a , & b , & c , & d , & k );
// 根据容斥原理，1<=x<=b&&1<=y<=d范围中的答案数减去1<=x<=b&&1<=y<=c-1范围中的答案数和
// 1<=x<=a-1&&1<=y<=d范围中的答案数再加上1<=x<=a-1&&1<=y<=c-1范围中的答案数
// 即可得到a<=x<=b&&c<=y<=d范围中的答案数
// 这一步如果不懂可以画坐标图进行理解
printf ( "%d \n " , solve ( b / k , d / k ) - solve ( b / k , ( c - 1 ) / k ) -
solve (( a - 1 ) / k , d / k ) +
solve (( a - 1 ) / k , ( c - 1 ) / k ));
}
return 0 ;
}
求值（多組數據）
\[
\sum_{i=1}^n \operatorname{lcm}(i,n)\quad \text{s.t.}\ 1\leqslant T\leqslant 3\times 10^5,1\leqslant n\leqslant 10^6
\]
易得原式即
\[
\sum_{i=1}^n \frac{i\cdot n}{\gcd(i,n)}
\]
將原式複製一份並且顛倒順序，然後將 n 一項單獨提出，可得
\[
\frac{1}{2}\cdot \left(\sum_{i=1}^{n-1}\frac{i\cdot n}{\gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i\cdot n}{\gcd(i,n)}\right)+n
\]
根據 \(\gcd(i,n)=\gcd(n-i,n)\) ，可將原式化為
\[
\frac{1}{2}\cdot \left(\sum_{i=1}^{n-1}\frac{i\cdot n}{\gcd(i,n)}+\sum_{i=n-1}^{1}\frac{i\cdot n}{\gcd(n-i,n)}\right)+n
\]
兩個求和式中分母相同的項可以合併。
\[
\frac{1}{2}\cdot \sum_{i=1}^{n-1}\frac{n^2}{\gcd(i,n)}+n
\]
即
\[
\frac{1}{2}\cdot \sum_{i=1}^{n}\frac{n^2}{\gcd(i,n)}+\frac{n}{2}
\]
可以將相同的 \(\gcd(i,n)\) 合併在一起計算，故只需要統計 \(\gcd(i,n)=d\) 的個數。當 \(\gcd(i,n)=d\) 時，\(\displaystyle\gcd(\frac{i}{d},\frac{n}{d})=1\) ，所以 \(\gcd(i,n)=d\) 的個數有 \(\displaystyle\varphi(\frac{n}{d})\) 個。
故答案為
\[
\frac{1}{2}\cdot\sum_{d\mid n}\frac{n^2\cdot\varphi(\frac{n}{d})}{d}+\frac{n}{2}
\]
變換求和順序，設 \(\displaystyle d'=\frac{n}{d}\) ，合併公因式，式子化為
\[
\frac{1}{2}n\cdot\left(\sum_{d'\mid n}d'\cdot\varphi(d')+1\right)
\]
設 \(\displaystyle \operatorname{g}(n)=\sum_{d\mid n} d\cdot\varphi(d)\) ，已知 \(\operatorname{g}\) 為積性函數，於是可以 \(\Theta(n)\) 篩出。每次詢問 \(\Theta(1)\) 計算即可。
下面給出這個函數篩法的推導過程：
首先考慮 \(\operatorname g(p_j^k)\) 的值，顯然它的約數只有 \(p_j^0,p_j^1,\cdots,p_j^k\) ，因此
\[
\operatorname g(p_j^k)=\sum_{w=0}^{k}p_j^w\cdot\varphi(p_j^w)
\]
又有 \(\varphi(p_j^w)=p_j^{w-1}\cdot(p_j-1)\) ，則原式可化為
\[
\sum_{w=0}^{k}p_j^{2w-1}\cdot(p_j-1)
\]
於是有
\[
\operatorname g(p_j^{k+1})=\operatorname g(p_j^k)+p_j^{2k+1}\cdot(p_j-1)
\]
那麼，對於線性篩中的 \(\operatorname g(i\cdot p_j)(p_j|i)\) ，令 \(i=a\cdot p_j^w(\operatorname{gcd}(a,p_j)=1)\) ，可得
\[
\operatorname g(i\cdot p_j)=\operatorname g(a)\cdot\operatorname g(p_j^{w+1})
\]
\[
\operatorname g(i)=\operatorname g(a)\cdot\operatorname g(p_j^w)
\]
即
\[
\operatorname g(i\cdot p_j)-\operatorname g(i)=\operatorname g(a)\cdot p_j^{2w+1}\cdot(p_j-1)
\]
同理有
\[
\operatorname g(i)-\operatorname g(\frac{i}{p_j})=\operatorname g(a)\cdot p_j^{2w-1}\cdot(p_j-1)
\]
因此
\[
\operatorname g(i\cdot p_j)=\operatorname g(i)+\left (\operatorname g(i)-\operatorname g(\frac{i}{p_j})\right )\cdot p_j^2
\]
時間複雜度 ：\(\Theta(n+T)\)
代碼實現
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 #include <cstdio>
const int N = 1000000 ;
int tot , p [ N + 5 ];
long long g [ N + 5 ];
bool flg [ N + 5 ]; // 标记数组
void solve () {
g [ 1 ] = 1 ;
for ( int i = 2 ; i <= N ; ++ i ) {
if ( ! flg [ i ]) {
p [ ++ tot ] = i ;
g [ i ] = ( long long ) 1 * i * ( i - 1 ) + 1 ;
}
for ( int j = 1 ; j <= tot && i * p [ j ] <= N ; ++ j ) {
flg [ i * p [ j ]] = 1 ;
if ( i % p [ j ] == 0 ) {
g [ i * p [ j ]] =
g [ i ] + ( g [ i ] - g [ i / p [ j ]]) * p [ j ] * p [ j ]; // 代入推出来的式子
break ;
}
g [ i * p [ j ]] = g [ i ] * g [ p [ j ]];
}
}
}
int main () {
int T , n ;
solve (); // 预处理g数组
scanf ( "%d" , & T );
for ( int i = 1 ; i <= T ; ++ i ) {
scanf ( "%d" , & n );
printf ( "%lld \n " , ( g [ n ] + 1 ) * n / 2 );
}
return 0 ;
}
求值（對 \(20101009\) 取模）
\[
\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)\qquad (n,m\leqslant 10^7)
\]
易知原式等價於
\[
\sum_{i=1}^n\sum_{j=1}^m\frac{i\cdot j}{\gcd(i,j)}
\]
枚舉最大公因數 \(d\) ，顯然兩個數除以 \(d\) 得到的數互質
\[
\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid i,d\mid j,\gcd(\frac{i}{d},\frac{j}{d})=1}\frac{i\cdot j}{d}
\]
非常經典的 \(\gcd\) 式子的化法
\[
\sum_{d=1}^n d\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]\ i\cdot j
\]
後半段式子中，出現了互質數對之積的和，為了讓式子更簡潔就把它拿出來單獨計算。於是我們記
\[
\operatorname{sum}(n,m)=\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=1]\ i\cdot j
\]
接下來對 \(\operatorname{sum}(n,m)\) 進行化簡。首先枚舉約數，並將 \([\gcd(i,j)=1]\) 表示為 \(\varepsilon(\gcd(i,j))\)
\[
\sum_{d=1}^n\sum_{d\mid i}^n\sum_{d\mid j}^m\mu(d)\cdot i\cdot j
\]
設 \(i=i'\cdot d\) ，\(j=j'\cdot d\) ，顯然式子可以變為
\[
\sum_{d=1}^n\mu(d)\cdot d^2\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\cdot j
\]
觀察上式，前半段可以預處理前綴和；後半段又是一個範圍內數對之和，記
\[
g(n,m)=\sum_{i=1}^n\sum_{j=1}^m i\cdot j=\frac{n\cdot(n+1)}{2}\times\frac{m\cdot(m+1)}{2}
\]
可以 \(\Theta(1)\) 求解
至此
\[
\operatorname{sum}(n,m)=\sum_{d=1}^n\mu(d)\cdot d^2\cdot g(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)
\]
我們可以 \(\lfloor\frac{n}{\lfloor\frac{n}{d}\rfloor}\rfloor\) 數論分塊求解 \(\operatorname{sum}(n,m)\) 函數。
在求出 \(\operatorname{sum}(n,m)\) 後，回到定義 \(\operatorname{sum}\) 的地方，可得原式為
\[
\sum_{d=1}^n d\cdot\operatorname{sum}(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)
\]
可見這又是一個可以數論分塊求解的式子！
本題除了推式子比較複雜、代碼細節較多之外，是一道很好的莫比烏斯反演練習題！（上述過程中，默認 \(n\leqslant m\) ）
時間複雜度：\(\Theta(n+m)\) （瓶頸為線性篩）
代碼實現
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 #include <algorithm>
#include <cstdio>
using namespace std ;
const int N = 1e7 ;
const int mod = 20101009 ;
int n , m , mu [ N + 5 ], p [ N / 10 + 5 ], sum [ N + 5 ];
bool flg [ N + 5 ];
int Sum ( int x , int y ) {
return (( long long ) 1 * x * ( x + 1 ) / 2 % mod ) *
(( long long ) 1 * y * ( y + 1 ) / 2 % mod ) % mod ;
}
int func ( int x , int y ) {
int res = 0 ;
int j ;
for ( int i = 1 ; i <= min ( x , y ); i = j + 1 ) {
j = min ( x / ( x / i ), y / ( y / i ));
res = ( res + ( long long ) 1 * ( sum [ j ] - sum [ i - 1 ] + mod ) *
Sum ( x / i , y / i ) % mod ) %
mod ; //+mod防负数
}
return res ;
}
int solve ( int x , int y ) {
int res = 0 ;
int j ;
for ( int i = 1 ; i <= min ( x , y ); i = j + 1 ) { // 整除分块处理
j = min ( x / ( x / i ), y / ( y / i ));
res = ( res + ( long long ) 1 * ( j - i + 1 ) * ( i + j ) / 2 % mod *
func ( x / i , y / i ) % mod ) %
mod ; // ！每步取模防爆
}
return res ;
}
void init () { // 线性筛
mu [ 1 ] = 1 ;
int tot = 0 , k = min ( n , m );
for ( int i = 2 ; i <= k ; ++ i ) {
if ( ! flg [ i ]) {
p [ ++ tot ] = i ;
mu [ i ] = -1 ;
}
for ( int j = 1 ; j <= tot && i * p [ j ] <= k ; ++ j ) {
flg [ i * p [ j ]] = 1 ;
if ( i % p [ j ] == 0 ) {
mu [ i * p [ j ]] = 0 ;
break ;
}
mu [ i * p [ j ]] = - mu [ i ];
}
}
for ( int i = 1 ; i <= k ; ++ i )
sum [ i ] = ( sum [ i - 1 ] + ( long long ) 1 * i * i % mod * ( mu [ i ] + mod )) % mod ;
}
int main () {
scanf ( "%d%d" , & n , & m );
init ();
printf ( "%d \n " , solve ( n , m ));
}
多組數據，求
\[
\sum_{i=1}^n\sum_{j=1}^md(i\cdot j) \qquad \left(n,m,T\leq5\times10^4\right)
\]
其中 \(d(n)=\sum_{i \mid n}1\) ，\(d(n)\) 表示 \(n\) 的約數個數
要推這道題首先要了解 \(d\) 函數的一個特殊性質
\[
d(i\cdot j)=\sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)=1]
\]
再化一下這個式子
\[
\begin{aligned}
d(i\cdot j)=&\sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)=1]\\
=&\sum_{x \mid i}\sum_{y \mid j}\sum_{p \mid \gcd(x,y)}\mu(p)\\
=&\sum_{p=1}^{min(i,j)}\sum_{x \mid i}\sum_{y \mid j}[p \mid \gcd(x,y)]\cdot\mu(p)\\
=&\sum_{p \mid i,p \mid j}\mu(p)\sum_{x \mid i}\sum_{y \mid j}[p \mid \gcd(x,y)]\\
=&\sum_{p \mid i,p \mid j}\mu(p)\sum_{x \mid \frac{i}{p}}\sum_{y \mid \frac{j}{p}}1\\
=&\sum_{p \mid i,p \mid j}\mu(p)d\left(\frac{i}{p}\right)d\left(\frac{j}{p}\right)\\
\end{aligned}
\]
將上述式子代回原式
\[
\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^md(i\cdot j)\\
=&\sum_{i=1}^n\sum_{j=1}^m\sum_{p \mid i,p \mid j}\mu(p)d\left(\frac{i}{p}\right)d\left(\frac{j}{p}\right)\\
=&\sum_{p=1}^{min(n,m)}
\sum_{i=1}^n\sum_{j=1}^m
[p \mid i,p \mid j]\cdot\mu(p)d\left(\frac{i}{p}\right)d\left(\frac{j}{p}\right)\\
=&\sum_{p=1}^{min(n,m)}
\sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}
\mu(p)d(i)d(j)\\
=&\sum_{p=1}^{min(n,m)}\mu(p)
\sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}d(i)
\sum_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}d(j)\\
=&\sum_{p=1}^{min(n,m)}\mu(p)
S\left(\left\lfloor\frac{n}{p}\right\rfloor\right)
S\left(\left\lfloor\frac{m}{p}\right\rfloor\right)
\left(S(n)=\sum_{i=1}^{n}d(i)\right)\\
\end{aligned}
\]
那麼 \(O(n)\) 預處理 \(\mu,d\) 的前綴和，\(O(\sqrt{n})\) 分塊處理詢問，總複雜度 \(O(n+T\sqrt{n})\) .
代碼實現
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 #include <algorithm>
#include <cstdio>
using namespace std ;
const long long N = 5e4 + 5 ;
long long n , m , T , pr [ N ], mu [ N ], d [ N ], t [ N ],
cnt ; // t 表示 i 的最小质因子出现的次数
bool bp [ N ];
void prime_work ( long long k ) {
bp [ 0 ] = bp [ 1 ] = 1 , mu [ 1 ] = 1 , d [ 1 ] = 1 ;
for ( long long i = 2 ; i <= k ; i ++ ) { // 线性筛
if ( ! bp [ i ]) pr [ ++ cnt ] = i , mu [ i ] = -1 , d [ i ] = 2 , t [ i ] = 1 ;
for ( long long j = 1 ; j <= cnt && i * pr [ j ] <= k ; j ++ ) {
bp [ i * pr [ j ]] = 1 ;
if ( i % pr [ j ] == 0 ) {
mu [ i * pr [ j ]] = 0 ;
d [ i * pr [ j ]] = d [ i ] / ( t [ i ] + 1 ) * ( t [ i ] + 2 );
t [ i * pr [ j ]] = t [ i ] + 1 ;
break ;
} else {
mu [ i * pr [ j ]] = - mu [ i ];
d [ i * pr [ j ]] = d [ i ] << 1 ;
t [ i * pr [ j ]] = 1 ;
}
}
}
for ( long long i = 2 ; i <= k ; i ++ )
mu [ i ] += mu [ i - 1 ], d [ i ] += d [ i - 1 ]; // 求前缀和
}
long long solve () {
long long res = 0 , mxi = min ( n , m );
for ( long long i = 1 , j ; i <= mxi ; i = j + 1 ) { // 整除分块
j = min ( n / ( n / i ), m / ( m / i ));
res += d [ n / i ] * d [ m / i ] * ( mu [ j ] - mu [ i - 1 ]);
}
return res ;
}
int main () {
scanf ( "%lld" , & T );
prime_work ( 50000 ); // 预处理
while ( T -- ) {
scanf ( "%lld%lld" , & n , & m );
printf ( "%lld \n " , solve ());
}
return 0 ;
}
莫比烏斯反演擴展
結尾補充一個莫比烏斯反演的非卷積形式。
對於數論函數 \(f,g\) 和完全積性函數 \(t\) 且 \(t(1)=1\) ：
\[
\begin{gathered}
f(n)=\sum_{i=1}^nt(i)g\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\
\iff\\
g(n)=\sum_{i=1}^n\mu(i)t(i)f\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
\end{gathered}
\]
我們證明一下
\[
\begin{aligned}
g(n)&=\sum_{i=1}^n\mu(i)t(i)f\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\
&=\sum_{i=1}^n\mu(i)t(i)
\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}t(j)
g\left(\left\lfloor\frac{\left\lfloor\frac{n}{i}\right\rfloor}{j}\right\rfloor\right)\\
&=\sum_{i=1}^n\mu(i)t(i)
\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}t(j)
g\left(\left\lfloor\frac{n}{ij}\right\rfloor\right)\\
&=\sum_{T=1}^n
\sum_{i=1}^n\mu(i)t(i)
\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}[ij=T]
t(j)g\left(\left\lfloor\frac{n}{T}\right\rfloor\right)
&\text{【先枚舉 ij 乘積】}\\
&=\sum_{T=1}^n
\sum_{i \mid T}\mu(i)t(i)
t\left(\frac{T}{i}\right)g\left(\left\lfloor\frac{n}{T}\right\rfloor\right)
&\text{【}\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}[ij=T] \text{對答案的貢獻為 1，於是省略】}\\
&=\sum_{T=1}^ng\left(\left\lfloor\frac{n}{T}\right\rfloor\right)
\sum_{i \mid T}\mu(i)t(i)t\left(\frac{T}{i}\right)\\
&=\sum_{T=1}^ng\left(\left\lfloor\frac{n}{T}\right\rfloor\right)
\sum_{i \mid T}\mu(i)t(T)
&\text{【t 是完全積性函數】}\\
&=\sum_{T=1}^ng\left(\left\lfloor\frac{n}{T}\right\rfloor\right)t(T)
\sum_{i \mid T}\mu(i)\\
&=\sum_{T=1}^ng\left(\left\lfloor\frac{n}{T}\right\rfloor\right)t(T)
\varepsilon(T)
&\text{【}\mu\ast 1= \varepsilon\text{】}\\
&=g(n)t(1)
&\text{【當且僅當 T=1,}\varepsilon(T)=1\text{時】}\\
&=g(n)
& \square
\end{aligned}
\]
參考文獻
algocode 算法博客
更新历史 在 GitHub 上编辑此页！ hydingsy, hyp1231, ranwen, 383494 CC BY-SA 4.0 和 SATA