Luogu P1829 [国家集训队]Crash的数字表格

题目链接: https://www.luogu.org/problemnew/show/P1829

显然,题目所求为以下式子

以下均默认$n \leq m$

$$
\sum_{i = 1}^n \sum_{j = 1}^m lcm(i,j)
$$

先来一些比较显然的东西
$$
\begin{aligned}
\sum_{i = 1}^n \sum_{j = 1}^m lcm(i,j) & =
\sum_{i = 1}^n \sum_{j = 1}^n \frac{i \cdot j}{\gcd(i,j)}\\
& = \sum_{d = 1}^n d \sum_{i = 1}^{\frac{n}{d}} \sum_{j = 1}^{\frac{m}{d}} i \cdot j \cdot [\gcd(i,j) = 1]\\
\end{aligned}
$$
后面一段看起来还可以再加优化

Continue reading “Luogu P1829 [国家集训队]Crash的数字表格”