给我自己的博客打个广告，关于莫比乌斯反演和整除分块上面有详细的讲解。

首先，我们求简化版问题：求 $\displaystyle{\sum_{i = 1}^n\sum_{j = 1}^m[(i, j) = 1]}$。

利用 莫比乌斯反演 + 整除分块 我们可以用 $O(\sqrt n)$ 的时间复杂度求解。

注意到，$[(i, j) = 1] = \varepsilon((i, j)) = \sum_{d \mid (i, j)}\mu(d)$。因此该题等价于求

$\displaystyle{\sum_{i = 1}^n \sum_{j = 1}^m \sum_{d \mid (i, j)}\mu(d)}$

交换求和顺序，有

$\displaystyle{\sum_{d = 1}\mu(d)\sum_{i = 1}^n[d \mid i]\sum_{j = 1}^m[d \mid j]}$

注意到，$1 \sim n$ 中 $d$ 的倍数有 $\lfloor \frac{n}{d} \rfloor$ 个，因此 $\sum_{i = 1}^n[d \mid i] = \lfloor \frac{n}{d} \rfloor$，因此有

$\displaystyle{\sum_{d = 1}^{\min(n, m)} \mu(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor}$

接下来，就可以用 整除分块 来求解了。

回到本题，我们将和式展开，有

$\begin{align} \sum_{i = a}^n\sum_{j = b}^m[(i, j) = 1] &= \sum_{i = 1}^n\sum_{j = b}^m\sum_{d \mid i, d \mid j}\mu(d) - \sum_{i = 1}^{a - 1}\sum_{j = b}^m\sum_{d \mid i, d \mid j}\mu(d) \\ &= \sum_{i = 1}^n\sum_{j = 1}^m\sum_{d \mid i, d \mid j}\mu(d) - \sum_{i = 1}^n\sum_{j = 1}^{b - 1}\sum_{d \mid i, d \mid j}\mu(d) - \\ & \quad \enspace \sum_{i= 1}^{a - 1}\sum_{j = 1}^m\sum_{d \mid i, d \mid j}\mu(d) + \sum_{i = 1}^{a - 1}\sum_{j = 1}^{b - 1}\sum_{d \mid i, d \mid j}\mu(d) \end{align}$

于是转化为了四个上面的简化版问题。

实际上，简化版问题也有对应的题目，可以直接水掉。

3220. [SDOI 2008] 仪仗队

3609. [BZOJ 1101] Zap