简单推一下今天的式子。
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})$ 做的。
今天其他几道题太水了，没啥好写的。