「Summary」2022-07-18 做题记录

简单推一下今天的式子。

2022-07-18

$\mathbb{[NOI2010]能量采集}$

link
$$ \begin{matrix} &\sum_{i = 1}^{n} \sum_{j = 1}^{m} (2 \gcd(i, j) - 1) \\ =&2\sum_{i = 1}^{n} \sum_{j = 1}^{m} \gcd(i, j) - nm \end{matrix} $$
显然，集中尽力化掉 $\sum_{i = 1}^{n} \sum_{i = 1}^{m} \gcd(i, j)$ 即可。
一个朴实的想法是枚举 $\gcd(i, j)$ 的取值。
$$ \begin{matrix} =&\sum_{g = 1}^{\min(n, m)} g \sum_{i = 1}^{\lfloor \frac{n}{g} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{g} \rfloor} [\gcd(i, j) = 1] \\ =&\sum_{g = 1}^{\min(n, m)} g \sum_{i = 1}^{\lfloor \frac{n}{g} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{g} \rfloor} \sum_{d \mid \gcd(i, j)} \mu(d) \\ \end{matrix} $$
改变枚举顺序。
$$ \begin{matrix} =&\sum_{g = 1}^{\min(n, m)} g \sum_{d = 1}^{\min(\lfloor \frac{n}{g} \rfloor, \lfloor \frac{m}{g} \rfloor)} \mu(d) \lfloor \frac{n}{gd} \rfloor \lfloor \frac{m}{gd} \rfloor\\ \end{matrix} $$
后面一坨是 $\sqrt{n}$ 可以整除分块做的，总的复杂度是 $\Theta(n \sqrt{n})$。
哦，我是🐖，整除分块都不用，这玩意是个调和级数。
总结：如果我在 4 岁时参加了国赛，我应该能过这道题。

$\mathbb{YY的GCD}$

link
这道题是原来写过的，可以参考 Mobius & Dirichlet Solution Set 的题解，既然今天又碰到了，那就再推一遍。
令所有素数组成的集合为 $\mathbb{P}$ 。

$$ \begin{aligned} & \sum_{i = 1}^{n} \sum_{j = 1}^{m} [\gcd(i, j) \in \mathbb{P}] \\ = & \sum_{p \in \mathbb{P}} \sum_{i = 1}^{n} \sum_{j = 1}^{m} [\gcd(i, j) = p] \\ = & \sum_{p \in \mathbb{P}} \sum_{i = 1}^{\lfloor \frac{n}{p} \rfloor} \sum_{i = 1}^{\lfloor \frac{n}{p} \rfloor} [\gcd(i, j) = 1] \\ = & \sum_{p \in \mathbb{P}} \sum_{d = 1}^{\min(\lfloor \frac{n}{p} \rfloor, \lfloor \frac{m}{p} \rfloor)} \mu(d) \lfloor \frac{n}{pd} \rfloor \lfloor \frac{m}{pd} \rfloor \end{aligned} $$

令 $pd = T$ 。
$$ \begin{aligned} = & \sum_{p \in \mathbb{P}} \sum_{d = 1}^{\min(\lfloor \frac{n}{p} \rfloor, \lfloor \frac{m}{p} \rfloor)} \mu(d) \lfloor \frac{n}{pd} \rfloor \lfloor \frac{m}{pd} \rfloor \\ = & \sum_{T = 1}^{n} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{p \mid T} \mu(\frac{T}{p}) \\ \end{aligned} $$
这个玩意是可以不带任何技巧直接 $\Theta(n\sqrt{n})$ 做的。

今天其他几道题太水了，没啥好写的。