莫比乌斯反演

莫比乌斯函数

定义

$$
x=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\
\mu(x) = \left{\begin{matrix}
0 & \text{if } \exists \alpha_i \ge2 \
(-1)^k & \text{if } \forall \alpha_i = 1
\end{matrix}\right.
$$

性质

记 $S(n)= \sum_{d|n} \mu(d)$ ，那么 $S(n) = \left{\begin{matrix}
1 & \text{if } n=1\
0 & \text{if } n>1
\end{matrix}\right.$

莫比乌斯反演

若 $F(n)=\sum_{d|n} f(d)$ ，则 $f(n)=\sum_{d|n}\mu(d)F(\frac n d)$

若 $F(n)=\sum_{n|d} f(d)$ ，则 $f(n)=\sum_{n|d}\mu(\frac d n)F(d)$

例题1：洛谷 P2522 [HAOI2011] Problem b/AcWing 2702. problem b

对于给出的 $ n $ 个询问，每次求有多少个数对 $ (x,y) $，满足 $ a≤x≤b，c≤y≤d $，且 $ \text{gcd}(x,y) = k $，$ \text{gcd}(x,y) $ 函数为 $ x $ 和 $ y $ 的最大公约数。

输入格式

第一行一个整数 $ n $。

接下来 $ n $ 行每行五个整数，分别表示 $ a、b、c、d、k $。

输出格式

共 $ n $ 行，每行一个整数表示满足要求的数对 $ (x,y) $ 的个数。

数据范围

$ 1 \le n \le 50000 $,
$ 1 \le a \le b \le 50000 $,
$ 1 \le c \le d \le 50000 $,
$ 1 \le k \le 50000 $

输入样例：

1 2 3

2 2 5 1 5 1 1 5 1 5 2

输出样例：

1 2

14 3

分析：

记答案为 $S$ ，$S=S_{b,d}-S_{a-1,d}-S_{b,c-1}+S_{a-1,c-1}$，转化为求 $1 \le x \le a,1\le y \le b$ 的结果（前缀和）

定义 $F(n)=\sum_{x=1}^a\sum_{y=1}^ b [n|(x,y)] $ （ 满足 $1 \le x \le a , 1 \le y \le b , n|(x,y)$ 的点 $(x,y)$ 的数量），$f(n)=\sum_{x=1}^a \sum_{y=1}^b[(x,y)=n]$（ 满足 $1 \le x \le a , 1 \le y \le b , (x,y)=n$ 的点 $(x,y)$ 的数量）

则 $F(n)=\sum_{n|d} f(d)$，因此可以使用莫比乌斯反演，$f(n)=\sum_{n|d} \mu(\frac d n) F(d)$

考虑如何求 $F(d)$，由于$d|(x,y)$，所以 $d|x,d|y$ ，所以 $F(d)=\lfloor \frac a d \rfloor \lfloor \frac b d \rfloor$，所以 $f(n)=\sum_{n|d} \mu(\frac d n) \lfloor \frac a d \rfloor \lfloor \frac b d \rfloor$

记 $d’=\frac d n$（$d’=1,2,\cdots$ ），则 $d=d’n$ ，$f(n)=\sum_{d’} \mu(d’) \lfloor \frac a {d’n} \rfloor \lfloor \frac b {d’n} \rfloor$

由于 $a,b,n$ 的取值与 $d’$ 无关，因此可以记 $a’=\frac a n,b’=\frac b n$ ，$f(n)=\sum_{d’} \mu(d’) \lfloor \frac {a’} {d’} \rfloor \lfloor \frac {b’} {d’} \rfloor$，此时直接求的复杂度为 $O(n)$

由于 $d’$ 的取值为 $1,2,\cdots$，由整数分块可知，可以将 $1\sim n$ 划分为 $O(\sqrt n)$ 段，在每一段中 $\lfloor \frac {a’} {d’} \rfloor \lfloor \frac {b’} {d’} \rfloor$ 的取值都相等，记这个值为 $c$，记一段的左端点为 $L$ ，右端点为 $R$ ，则这一段的值就为 $c\cdot[\mu(L)+\mu(L+1)+\cdots + \mu(R)]$，$\mu(i)$ 可以通过线性筛在 $O(n)$ 的时间复杂度内算出，可以使用前缀和将每次查询优化至 $O(1)$，因此计算每一段的值的时间复杂度为 $O(1)$，计算$f(n)$ 的时间复杂度为 $O(\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
53
54
55
56

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=5e4+5;

int primes[N],cnt,mu[N];
bool st[N];
int sum[N];

void init(){
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(!st[i])primes[cnt++]=i,mu[i]=-1;
        for(int j=0;primes[j]*i<N;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
            mu[primes[j]*i]=-mu[i];
//若mu[i]=0,则mu[p*i]=0,若mu[i]=1/-1，设mu[i]=(-1)^k，则mu[i*p]=(-1)^(k+1)=-mu[i]
        }
    }
    for(int i=1;i<N;i++){
        sum[i]=sum[i-1]+mu[i];
    }
}

int g(int k,int x){
    return k/(k/x);
}

ll f(int a,int b,int k){
    a=a/k,b=b/k;//a->a',b->b'
    ll res=0;
    int n=min(a,b);
    //整数分块
    for(int l=1,r;l<=n;l=r+1){
        r=min(n,min(g(a,l),g(b,l)));
        res+=1ll*(sum[r]-sum[l-1])*(a/l)*(b/l);
    }
    return res;
}

int main(){
    
    init();
    
    int T;
    cin >> T;
    while(T--){
        int a,b,c,d,k;
        cin >> a >> b >> c >> d >> k;
        cout << f(b,d,k)-f(a-1,d,k)-f(b,c-1,k)+f(a-1,c-1,k) << endl;
    }
    return 0;
}

例题2：洛谷 P3327 [SDOI2015] 约数个数和/AcWing 1358. 约数个数和

设 $ d(x) $ 为 $ x $ 的约数个数，给定 $ N,M $，求

$$
\sum_{i=1}^N\sum_{j=1}^Md(ij)
$$

输入格式

输入多组测试数据。

第一行，一个整数 $ T $，表示测试数据的组数。

接下来的 $ T $ 行，每行两个整数 $ N、M $。

输出格式

$ T $ 行，每行一个整数，表示你所求的答案。

数据范围

$ 1 \le N,M,T \le 50000 $

输入样例：

1 2 3

2 7 4 5 6

输出样例：

1 2

110 121

分析：

引理：$d(ij)=\sum_{x|i} \sum_{y|j} [(x,y)=1]$

引理证明：

先考虑左边，设 $i=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k},j=p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}$，则 $ij=p_1^{\alpha_1+\beta_1}p_2^{\alpha_2+\beta_2}\cdots p_k^{\alpha_k+\beta_k}$，$d(ij)=(\alpha_1+\beta_1+1)(\alpha_2+\beta_2+1)\cdots(\alpha_k+\beta_k+1)$

再考虑右边，先考虑 $x,y$ 是 $p_1$ 的倍数的情况，当 $x=1$ 时，$y$ 可以取 $1,p_1,p_1^2 ,\cdots , p_1^{\beta_1}$ ， $y=1$ 时

$x$ 可以取 $1,p_1,p_1^2 ,\cdots , p_1^{\alpha_1}$，而 $x,y$ 均不为 $1$ 时 $(x,y)$ 一定不为 $1$，因此一共 $ \alpha_1 +\beta_1 +1$ 种取法，同理，对于 $p_i$ ，有 $\alpha_i+\beta_i+1$ 中取法，因此总的取法为 $(\alpha_1+\beta_1+1)(\alpha_2+\beta_2+1)\cdots(\alpha_k+\beta_k+1)$

综上，左边等于右边，引理得证

由引理得：
$$
\sum_{i=1}^N\sum_{j=1}^M d(ij)=\sum_{i=1}^N\sum_{j=1}^M\sum_{x|i} \sum_{y|j} [(x,y)=1]
$$
设 $F(n)=\sum_{i=1}^N\sum_{j=1}^M\sum_{x|i}\sum_{y|j}[n|(x,y)]$，$f(n)=\sum_{i=1}^N\sum_{j=1}^M\sum_{x|i}\sum_{y|j}[(x,y)=n]$

则 $F(n)=\sum_{n|d} f(d)$，所以 $f(n)=\sum_{n|d} \mu(\frac d n) F(d)$

因此，问题转化为求 $f(1)$

$f(1)=\sum_{d=1}^{\min(N,M)} \mu(d) F(d)$

下面考虑如何求 $F(d)$
$$
F(n)=\sum_{i=1}^N\sum_{j=1}^M\sum_{x|i}\sum_{y|j}[n|(x,y)]=\sum_{x=1}^N\sum_{y=1}^M \lfloor\frac N x \rfloor \lfloor \frac M y \rfloor [n|(x,y)]
$$
由于 $n|(x,y)$，所以 $n|x,n|y$。设 $x’=\frac x n,y’=\frac y n$，则
$$
F(n)=\sum_{x=1}^N\sum_{y=1}^M \lfloor\frac N x \rfloor \lfloor \frac M y \rfloor [n|(x,y)]=\sum_{x’=1}^{\frac N n}\sum_{y’=1}^{\frac M n} \lfloor\frac N {nx’} \rfloor \lfloor \frac M {ny’} \rfloor
$$
记 $N’=\frac N n,M’=\frac M n$，则
$$
F(n)=\sum_{x’=1}^{\frac N n}\sum_{y’=1}^{\frac M n} \lfloor\frac N {nx’} \rfloor \lfloor \frac M {ny’} \rfloor=\sum_{i=1}^{N’}\sum_{j=1}^{M’} \lfloor\frac {N’} {x’} \rfloor \lfloor \frac {M’} {y’} \rfloor
$$
记 $a_i=\lfloor \frac {N’} i \rfloor,b_j=\lfloor \frac{M’} j \rfloor$，则
$$
F(n)=\sum_{i=1}^{N’}\sum_{j=1}^{M’} \lfloor\frac {N’} {x’} \rfloor \lfloor \frac {M’} {y’} \rfloor=\sum_{i=1}^{N’}\sum_{j=1}^{M’} a_i b_j=(\sum_{i=1}^{N’}a_i)(\sum_{j=1}^{M’}b_j)
$$
记 $h(k)=\sum_{i=1}^k \lfloor \frac k i \rfloor$，则
$$
F(n)=(\sum_{i=1}^{N’}a_i)(\sum_{j=1}^{M’}b_j)=h(N’)\cdot h(M’)
$$
所以
$$
f(1)=\sum_{d=1}^{\min(N,M)} \mu(d) F(d)=\sum_{d=1}^{\min(N,M)} \mu(d) \cdot h(\frac N d) \cdot h(\frac M d)
$$
由于 $h(x)$ 的取值完全取决于 $x$ ，因此可以使用整数分块预处理所有的 $h(i)$，时间复杂度 $O(n\sqrt n)$

计算 $f(1)$ 时，也可以用整数分块计算每一段的 $h(\frac N d) \cdot h(\frac M d)$，使用前缀和计算每一段的 $\mu(d)$，时间复杂度 $O(\sqrt n)$

总时间复杂度 $O(n+n\sqrt n +q \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
53

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=5e4+5;

int primes[N],cnt,mu[N],sum[N],h[N];
bool st[N];

int g(int k,int x){
    return k/(k/x);
}

void init(){
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(!st[i])primes[cnt++]=i,mu[i]=-1;
        for(int j=0;primes[j]*i<N;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
            mu[i*primes[j]]=-mu[i];
        }
    }
    
    for(int i=1;i<N;i++){
        sum[i]=sum[i-1]+mu[i];
    }
    
    for(int i=1;i<N;i++){
        for(int l=1,r;l<=i;l=r+1){
            r=min(i,g(i,l));
            h[i]+=(r-l+1)*(i/l);
        }
    }
}

int main(){
    init();
    int T;
    cin >> T;
    while(T--){
        int n,m;
        cin >> n >> m;
        ll res=0;
        int k=min(n,m);
        for(int l=1,r;l<=k;l=r+1){
            r=min(k,min(g(n,l),g(m,l)));
            res+=1ll*(sum[r]-sum[l-1])*h[x/l]*h[m/l];
        }
        cout << res << endl;
    }
    return 0;
}