掌握莫反的核心：通过不断的变换枚举顺序和莫反的常见性质及推论，来把问题转换为一部分可以直接进行枚举，另一部分可以预处理的形式.

YY的GCD（洛谷P2257）

给定 N,MN, M，求 1≤x≤N1 \leq x \leq N，1≤y≤M1 \leq y \leq M 且 gcd⁡(x,y)\gcd(x, y) 为质数的 (x,y)(x, y) 有多少对。

输入格式

第一行一个整数 TT 表述数据组数。
接下来 TT 行，每行两个正整数，N,MN, M。

输出格式

TT 行，每行一个整数表示第 ii 组数据的结果。
T=104T = 10^4，N,M≤107N, M \leq 10^7。

由题意可知，让求：

∑i=1n∑j=1m[gcd(i,j)∈prime]\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]

按照莫反的套路，把枚举顺序改为先枚举gcdgcd，不妨令n≤mn\le m:

∑k=1n∑i=1n∑j=1m[gcd(i,j)=k]\sum_{k=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k],其中枚举的kk为质数.

把枚举上下界除以kk得：

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

这里直接使用莫反的推论：

[gcd(i,j)=1]=∑d∣gcd(i,j)μ(d)[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)

则原式变为：

∑k=1n∑i=1⌊nk⌋∑j=1⌊mk⌋∑d∣gcd(i,j)μ(d)\sum_{k=1}^n\sum_{i=1}^{\lfloor\frac{n}k\rfloor}\sum_{j=1}^{\lfloor\frac{m}k\rfloor}\sum_{d|gcd(i,j)}\mu(d)

继续按照套路，把dd提到第二层:

∑k=1n∑d=1n∑i=1⌊nkd⌋∑j=1⌊mkd⌋μ(d)\sum_{k=1}^n\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}\mu(d)

=∑k=1n∑d=1⌊nk⌋μ(d)∗⌊nkd⌋⌊mkd⌋=\sum_{k=1}^n\sum_{d=1}^{\lfloor\frac{n}k\rfloor}\mu(d)*\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor

令T=kdT=kd，带入得：

=∑k=1n∑d=1⌊nk⌋μ(d)∗⌊nT⌋⌊mT⌋=\sum_{k=1}^n\sum_{d=1}^{\lfloor\frac{n}k\rfloor}\mu(d)*\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor

把最外层变为枚举TT得：

∑T=1n⌊nT⌋⌊mT⌋∑k∣T,k∈primeμ(Tk)\sum_{T=1}^n\lfloor\frac{n}T\rfloor\lfloor\frac{m}T\rfloor\sum_{k|T,k\in prime}\mu(\frac{T}k)

我们可以枚举每个质数kk，然后枚举每个质数的倍数，对于kk的倍数将它加上贡献μ(Tk)\mu(\frac{T}k)

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1e7 + 100;

LL primes[N] , mul[N] , sum[N];
int cnt;
bool st[N];

void init(int x){
    mul[1] = 1;
    for(int i = 2 ; i <= x ; i ++){
        if(!st[i]){
            primes[cnt ++] = i;
            mul[i] = -1;
        }
        for(int j = 0 ; j < cnt && primes[j] <= x / i ; j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0){
                mul[primes[j] * i] = 0;
                break;
            }
            mul[primes[j] * i] = -mul[i];
        }
    }
    for(int i = 0 ; i < cnt ; i ++)
        for(int j = 1 ; primes[i] * j <= x ; j ++)
            sum[primes[i] * j] += mul[j];
    for(int i = 1 ; i <= x ; i ++)
        sum[i] = sum[i - 1] + sum[i];
}

int main(){
    int T;
    cin >> T ;
    init(N - 50);
    while(T --){
        int n , m;
        cin >> n >> m;
        if(n < m)swap(n , m);
        LL res = 0;
        for(int l = 1 , r ; l <= m ; l = r + 1){
            r = min(n / (n / l) , m / (m / l));
            r = min(r , m);
            res += (LL)(n / l) * (LL)(m / l) *(sum[r] - sum[l - 1]);
        }
        printf("%lld\n" , res);
    }
    return 0;
}