预备知识：
- 数论函数：定义域为正整数的函数，如
- 单位函数：$\epsilon(n) = [n==1]$ 。
- 恒等函数：$id_k(n) = n^k$ ，$id_1(n)$ 通常简记为 $id(n)$ 。
- 常数函数：$1(n) = 1$ 。
- 除数函数：$\sigma_k(n) = \sum\limits_{d|n}d^k$ 。 $\sigma_0(n)$ 通常简记为 $d(n)$ 或 $r(n)$ ， $\sigma_1(n)$ 通常简记为 $\sigma(n)$ 。
- 欧拉函数：$\varphi(n) = \sum\limits_{i=1}^n[(i,n)==1]$ 。
- 莫比乌斯函数：$\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^{2}\mid n\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}$ ，其中 $\omega(n)$ 表示 $n$ 的本质不同质因子个数。
- 狄利克雷卷积：对于两个数论函数 $f(x)$ 和 $g(x)$ ，他们的狄利克雷卷积结果 $h(x)$ 定义为：$$h(x) = \sum \limits_{d|x}f(d)g(\frac{x}{d})=\sum \limits_{ab=x}f(a)g(b)$$ 可以简记为 $$h=f * g$$
- 狄利克雷卷积满足交换律，结合律，分配律。
- 莫比乌斯函数：
- 定义：$\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^{2}\mid n\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}$
- 性质：$\sum \limits_{d|n} \mu(d)= \begin{cases}1, & n=1, \ 0, & n \neq 1\end{cases}$ ，即 $\sum \limits_{d|n}\mu(d)=\epsilon(n),\mu * 1 = \epsilon$ ，证明如下
- 设 $n = \prod\limits_{i=1}^{k}p_i^{c_i},n’ = \prod\limits_{i=1}^{k}p_i$ ，那么 $\sum\limits_{d|n}\mu(d) = \sum\limits_{d|n’}\mu(d)=\sum\limits_{i=0}^k\binom{k}{i}·(-1)^i=(1+(-1))^k$ 。
- 根据二项式定理，易知该式子的值在 $k=0$ ，即 $n=1$ 时值为 $1$ ，否则为 $0$ ，即 $\sum \limits_{d|n}\mu(d)=\epsilon(n),\mu * 1 = \epsilon$ 。
- 推论：$[gcd(i, j)==1]=\sum\limits_{d|gcd(i,j)}\mu(d)$
例题：
求 $\sum \limits_{i=1}^{n} \sum \limits_{j=1}^{m} [gcd(i, j)=1]$ 。
因为 $gcd(i, j)=1$ 时对答案才有贡献，于是我们可以直接将其替换为 $\epsilon(gcd(i, j))$ ，故原式化为$$\sum \limits_{i=1}^{n} \sum \limits_{j=1}^{m} \epsilon(gcd(i, j))$$
将 $\epsilon$ 函数展开得到，$$\sum \limits_{i=1}^{n} \sum \limits_{j=1}^{m} \sum \limits_{d|gcd(i,j)}\mu(d)$$
变换求和顺序，先枚举 $d|gcd(i,j)$ 得到：$$\sum \limits_{d=1}\mu(d)\sum \limits_{i=1}^{n} [d|i]\sum \limits_{j=1}^{m} [d|j]$$
易知 $1\sim n$ 中 $d$ 的倍数有 $\lfloor \frac{n}{d}\rfloor$ 个，故原式化为 $$\sum \limits_{d=1}^{min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$$
很显然，式子可以用数论分块求解，时间复杂度 $O(n + T\sqrt{n})$ 。