UPD：狄利克雷卷积的单位元表示符号建议使用 $\epsilon$。

<h2>积性函数</h2>

<h3>定义</h3>

对于一个函数 $f$，若有 $\forall x,y,(x,y)=1,f(xy) = f(x)*f(y)$，则我们称这样的函数为积性函数。
举例：$\phi(x),\mu(i),d_k(n)$（$n$ 的所有正因子 $k$ 次幂和）

<h3>性质</h3>

若 $f(x)$ 为积性函数。
设 $n = \Pi p_i^{q_i}$，则有 $f(n) = \Pi f(p_i^{q_i})$。
这告诉我们大多数的积性函数都可以用线性筛来处理。
若 $f(x),g(x)$ 均为积性函数，那么下列的函数也是积性函数：
$$(fg)(n) = f(n)*g(n)$$
$$(f/g)(n) = f(n)/g(n)$$

<h2>Dirichlet 卷积</h2>

<h3>定义</h3>

定义在两个数论函数之间的运算 $\times$ 为：
$$(f \times g)(n) = \sum_{d|n} f(d)g(\frac{n}{d})$$
该运算满足交换律，结合律，分配律。
如果 $f,g$ 均为积性函数，那么 $f\times g$ 也是个积性函数。

<h3>单位元</h3>

定义 Dirichlet 卷积运算的单位元 $\iota(n)$。
显然该函数当 $n=1$ 的时候取 $1$，其他情况取 $0$。
一些关于单位元的例子：
对于任何数论函数 $f$, $f\times \iota = f$
单位元 $\iota = \mu \times i$
因数个数 $d = 1\times 1$
因数和 $\sigma = n\times 1$
欧拉函数 $\phi = mu \times ID$
定义一下函数乘法单位元 $u$ ，显然 $u(n) = 1$。

<h3>莫比乌斯函数</h3>

构造一个函数 $\mu$，使得 $\mu \times u = \iota$。
$\mu(x)$ 的取值：
如果 $x = 1,\mu(x) = 1$
如果 $x$ 含有平方因子，则 $\mu(x) = 0$
否则 $\mu(x) = (-1)^k$,$k$ 是 $x$ 的本质不同质因子个数。
易得 $\mu$ 是一个积性函数，可以用线性筛得到。
代码：

bool p[MAXN];
int prime[MAXN],mu[MAXN],cnt;

inline void pre(int limit){
    p[1] = true;mu[1] = 1;
    FOR(i,2,limit){
        if(!p[i]) prime[++cnt] = i,mu[i] = -1;
        for(Re int j = 1;j <= cnt && i*prime[j] <= limit;++j){
            p[i*prime[j]] = true;
            if(!(i%prime[j])) break;
            mu[i*prime[j]] = -mu[i];
        }
    }
}

接下来我们尝试证明 $\phi \times 1 = ID$,其中 $ID$ 为 $f(x) = x$。

首先由于 $\phi$ 是个积性函数，于是我们只需要证明当 $x' = p^c$ 时 $\mu \times 1 = \sum_{ d | x' } \phi ( \frac{ x' }{ d } ) = ID $ 成立即可。

因为 $p$ 是个质数，所以有 $d = p^0,p^1,p^2,...,p^c$。

随手推下式子：
$$ \phi \times i = \sum_{d | n} \phi( \frac{n}{d} )$$
$$ = \sum_{i=0}^c \phi(p^i)$$
$$ = 1 + (p-1) * \sum_{i=0}^c p^i$$
$$= p^c$$
$$= ID$$

<h2>莫比乌斯反演</h2>

现在我们来看看莫比乌斯反演讲了什么。
$$ f(n) = \sum_{d|n}g(d) \Leftrightarrow g(n) = \sum_{d|n} \mu(\frac{n}{d}) f(d) $$
写成卷积形式，即
$$f = g \times u \Leftrightarrow g = f \times \mu$$
我们来证明一下：
左边：
$$f = g \times u$$
$$\Rightarrow f \times \mu = g\times u\times \mu$$
$$\Rightarrow f\times \mu = g\times \iota$$
$$\Rightarrow f\times \mu = g$$
右边：
$$g = f\times \mu$$
$$\Rightarrow g\times u = f\times \mu*u$$
$$\Rightarrow g\times u = f\times \iota$$
$$\Rightarrow f = g\times u$$
证毕。
莫比乌斯反演的另一种常用形式：
$$ f(n) = \sum_{n|d} g(d) \Leftrightarrow g(n) = \sum_{n|d} \mu(\frac{d}{n}) f(d)$$。
接下来我们以一道例题来具体分析如何使用莫比乌斯反演解决问题。

<h2>「BZOJ 2820」YY 的 GCD</h2>

题目链接
注意：接下来所有的除法都向下取整。
定义质数组成的集合 $prime$，不难看出题目需要求：
$$\sum_{i=1}^n \sum_{j=1}^m [(i,j) \in prime] \tag 1$$
我们套路的设 $f(x)$ 表示 gcd 为 $x$ 的对数，即
$$f(x) = \sum_{i=1}^n \sum_{j=1}^m [(i,j)=x]$$
设 $F(x)$ 表示 gcd 为 $x$ 及 $x$ 的倍数的对数，即
$$F(x) = \sum_{x|d} f(d)$$
不难得出 $F(x) = \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{x} \rfloor$
根据莫比乌斯反演，可得
$$f(x) = \sum_{n|d} \mu(\frac{d}{n})F(d)$$
我们把 $(1)$ 式首先改为枚举质数 $p$。
$$Ans = \sum_{p \in prime}^{max(n,m)} \sum_{i=1}^n \sum_{j=1}^m [(i,j = p)]$$
代入 $f$，得
$$Ans = \sum_{p \in prime}^{max(n,m)} f(p)$$
然后根据上面莫比乌斯反演得到的结论，式子转化为
$$Ans = \sum_{p \in prime}^{max(n,m)} \sum_{p|d} \mu(\frac{d}{p})F(d)$$
我们枚举 $\frac{d}{p}$，得：
$$Ans = \sum_{p \in prime} \sum_{d=1}^{min(\frac{n}{p},\frac{m}{p})} \mu(d) F(dp) = \sum_{p \in prime} \sum_{d=1}^{min(\frac{n}{p},\frac{m}{p})} \mu(d) \lfloor \frac{n}{dp} \rfloor \lfloor \frac{m}{dp} \rfloor$$
设 $dp = T$，则

$$Ans = \sum_{T=1}^{ min(n,m) } \sum_{t|T,t \in prime} \mu(\frac{T}{t}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor$$
$$Ans = \sum_{T=1}^{min(n,m)} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor (\sum_{t|T} \mu(\frac{T}{t}))$$
推到这里我们已经可以通过预处理 $\mu$ 函数来 $O(n)$ 的做了。但是这一题是多组询问，注意到有除法，那么我们使用数论分块来使复杂度降低到 $\sqrt{n}$，处理个前缀和就可以了 $qwq$。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 10000000+5;
int prime[MAXN],mu[MAXN],g[MAXN],cnt;
bool p[MAXN];
LL sum[MAXN];

inline void pre(int limit){
    mu[1] = 1;
    FOR(i,2,limit){
        if(!p[i]){
            mu[i] = -1;prime[++cnt] = i;
        }
        for(Re int j = 1;j <= cnt && i*prime[j] <= limit;++j){
            p[i*prime[j]] = true;
            if(!(i%prime[j])) break;
            mu[prime[j]*i] = -mu[i];
        }
    }
    FOR(j,1,cnt) for(int i = 1;i  prime[j] <= limit;++i) g[iprime[j]] += mu[i];
    FOR(i,1,limit) sum[i] = sum[i-1] + 1ll*g[i];
}

inline void Solve(){
    int N,M;scanf("%d%d",&N,&M);
    LL ans = 0ll;if(N > M) std::swap(N,M);
    for(int l = 1,r;l <= N;l = r+1){
        r = std::min(N/(N/l),M/(M/l));
        ans += 1ll(N/l)(M/l)*(sum[r]-sum[l-1]);
        //DEBUG(sum[r]);DEBUG(sum[l-1]);
    }
    printf("%lldn",ans);
}

int main(){
    int T;scanf("%d",&T);pre(MAXN-2);
    while(T--) Solve();
    return 0;
}

<h2>总结：</h2>

可以把莫比乌斯反演理解成 “由大推小” ，即知道了如何 “由小推大” 后通过 $\mu$ 函数（可以理解为容斥系数）来快速求出小的函数。