开个坑，记录一些和反演以及狄利克雷卷积的东西。

首先积性函数、狄利克雷卷积等基本概念不写了，就讲讲性质吧。

有几个一定要记住的东西：

$$\mu \ast 1 = e$$

$$\varphi \ast 1 = id$$

$$\mu \ast id = \varphi$$

这几个在推式子的过程中都有很大的作用，务必要记住。

所谓莫比乌斯反演，其实就是：

$$F = f \ast 1\Leftrightarrow f = F \ast \mu$$

（谜之音：其实很多所谓“反演题”都没用到这俩性质啊……）

关于莫比乌斯函数本身，还有一个好康的性质：

$$(\mu\ast 1)(k) = \sum_{i = 0}^k (-1)^i C_k^i$$

[BZOJ 2301]Problem b

嗯……经典老题。

推导过程如下（很重要）：

$$\begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^m [gcd(i, j) = k] &= \sum_{i = 1}^{\lfloor \tfrac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \tfrac{m}{k} \rfloor} [gcd(i, j) = 1] \\ &= \sum_{i = 1}^{\lfloor \tfrac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \tfrac{m}{k} \rfloor} \sum_{d\mid i, d\mid j} \mu (d) \\ &= \sum_{d = 1}^{min(\lfloor \tfrac{n}{k} \rfloor, \lfloor \tfrac{m}{k} \rfloor)} \mu (d) \sum_{i = 1}^{\lfloor \tfrac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \tfrac{m}{k} \rfloor} [d\mid i, d\mid j] \\ &= \sum_{d = 1}^{min(\lfloor \tfrac{n}{k} \rfloor, \lfloor \tfrac{m}{k} \rfloor)} \mu (d)\lfloor\tfrac{n}{kd}\rfloor\lfloor\tfrac{m}{kd}\rfloor \end{aligned}$$

然后显然$\lfloor\tfrac{n}{kd}\rfloor\lfloor\tfrac{m}{kd}\rfloor$这个东西的取值是$O(\sqrt{n})$级别的，所以预处理欧拉筛然后搞出来$\mu$的前缀和，一次查询$O(\sqrt{n})$搞即可……

[BZOJ 2820]YY的GCD

劲啊……

用$p(x)$来表示$x$是否为素数（是的话返回1，否则返回0）。

然后大概就这样子：

$$\begin{align*} \sum_{i = 1}^n \sum_{j = 1}^m p(gcd(i, j)) & = \sum_{k = 1}^{min(n, m)} p(k) \sum_{d = 1}^{min(\lfloor \tfrac{n}{k} \rfloor, \lfloor \tfrac{m}{k} \rfloor)} \mu (d)\lfloor\tfrac{n}{kd}\rfloor\lfloor\tfrac{m}{kd}\rfloor \end{align*}$$

然后那个$kd$太不顺眼了，我们就直接枚举她吧！（逃

然后式子就变成了这样：

$$\sum_{T = 1}^{min(n, m)} \lfloor\tfrac{n}{T}\rfloor\lfloor\tfrac{m}{T}\rfloor\sum_{d\mid T} p(d)\mu(\tfrac{T}{d})$$

然后你发现了啥？中间那个$\sum_{d\mid T} p(d)\mu(\tfrac{T}{d})$不就是$(p\ast\mu)(T)$吗？于是乎问题的瓶颈变成了高效的预处理$p\ast\mu$。

不幸的事情是这个函数不是积性函数，但是线性筛还是可以做的吖！

然后我们大致就能归结出一个相当有用的式子：

$$\sum_{i = 1}^n \sum_{j = 1}^m p(gcd(i, j)) =  \sum_{T = 1}^{min(n, m)} \lfloor\tfrac{n}{T}\rfloor\lfloor\tfrac{m}{T}\rfloor\sum_{d\mid T} p(d)\mu(\tfrac{T}{d})$$

这个推导，是蛮有用的。