莫比乌斯反演

https://en.wikipedia.org/wiki/Möbius_function

积性函数

在数论中，积性函数是指一个定义域为正整数$n$的算术函数$f(n)$
有如下性质：$f(1) = 1$，且当$a$和$b$互质时，$f(ab) = f(a)f(b)$。

若当$a$和$b$不互质时，也有$f(ab) = f(a)f(b)$则称$f$为完全积性函数。

若$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$
则$f(n) = f(p_1^{a_1}) f(p_2^{a_2}) \cdots f(p_k^{a_k})$

常见的积性函数

欧拉函数：$\varphi(n)$
莫比乌斯函数：$\mu(n)$

常见的完全积性函数

幂函数：$f(n) = n^k$

两个重要等式

$$n = \sum_{i | n} \varphi(i)$$
$$[n = 1] = \sum_{i | n} \mu(i)$$

常见题目

求值（多组数据）
$$\sum_{i=1}^{n} \sum_{j=1}^{m} [\gcd(i, j) = 1]$$

原式等价于
$$\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d | \gcd(i, j)} \mu(d)$$
$$\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d | i, d | j} \mu(d)$$
$$\sum_{d} \mu(d) \left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor$$
然后$\left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor$只有$O(\sqrt{n} + \sqrt{m})$种可能，直接暴力即可。
总复杂度$O(n)$预处理，$O(\sqrt{n})$单次询问

更进一步可以通过杜教筛优化

参考题目

bzoj 2301