##莫比乌斯反演相关

###莫比乌斯函数

$$
\mu(n)=\left{\begin{array}{ll}
1 & \text { 若 } n=1 \
(-1)^{k} & \text { 若 } n \text { 无平方数因数，且 } n=p_{1} p_{2} \ldots \ldots p_{k} \
0 & \text { 若 } n \text { 有大于 } 1 \text { 的平方数因数。 }
\end{array}\right.
$$

设f(n)、g(n)是两个数论函数，它们的狄利克雷乘积也是一个数论函数，其定义为：

$$
\begin{aligned}
h(n)=& \sum_{d \mid n} f(d) g\left(\frac{n}{d}\right) \
& d>0
\end{aligned}
$$
若函数满足：
$$
f(n)=\sum_{d \mid n} g(d)=\sum_{d \mid n} g\left(\frac{n}{d}\right)
$$
则有
$$
g(n)=\sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right)=\sum_{d \mid n} \mu\left(\frac{n}{d}\right) f(d)
$$

###例题

求1<=i<=n,1<=j<=m，gcd(i,j)==d的对数。

先让n/=d,m/=d，变成求gcd(i,j)==1的对数。

$$
\begin{array}{l}
\sum_{i=1}^{n} \sum_{j=1}^{m}[\operatorname{gcd}(i, j)=1] \
=\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d \mid \operatorname{gcd}(i, j)}^{\min } \mu(d) \
=\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d|i, d| j}^{\min } \mu(d) \
=\sum_{d=1}^{\min } \mu(d) \sum_{d \mid i}^{n} \sum_{d \mid j}^{m} 1 \
=\sum_{d=1}^{\min } \mu(d) \frac{n}{d} \frac{m}{d}
\end{array}
$$
然后预处理出(d)的前缀和，O(sqrt(n))枚举d即可。

代码

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lli long long int
using namespace std;
const int maxn=5e4+1e2;

int mu[maxn];
lli sum[maxn];

inline void gen() {
    static int prime[maxn],cnt;
    static unsigned char vis[maxn];
    sum[1] = mu[1] = 1;
    for(int i=2;i<maxn;i++) {
        if( !vis[i] ) {
            prime[++cnt] = i,
            mu[i] = -1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<maxn;j++) {
            vis[i*prime[j]] = 1;
            mu[i*prime[j]] = -mu[i];
            if( ! ( i % prime[j]) ) {
                mu[i*prime[j]] = 0;
                break;
            }
        }
        sum[i] = sum[i-1] + mu[i];
    }
}

inline lli calc(int n,int m) {
    lli ret = 0;
    if( n > m )
        swap(n,m);
    int pos = 0;
    for(int i=1;i<=n;i=pos+1) {
        pos = min( n / ( n / i ) , m / ( m / i ) );
        ret += ( sum[pos] - sum[i-1] ) * ( n / i ) * ( m / i );
    }
    return ret;
}

int main() {
    static int T;
    int a,b,d;
    
    gen();
    
    scanf("%d",&T);
    
    while( T-- ) {
        scanf("%d%d%d",&a,&b,&d);
        a /= d , b /= d;
        printf("%lld\n",calc(a,b));
    }
    
    return 0;
}