日记

Mon May 26 2025

2 分钟

388 字

这 gbc 看的我有点 emo 怎么个事？

GCD - Extreme (II) Link to

我们发现他让我们求这个东西： $\sum\limits_{i = 1}^{n}\sum\limits_{j = i + 1}^{n}\gcd(i,j)$ ，显然可以转化一下：

\begin{aligned} & \sum_{i = 1}^{n}\sum_{j = i + 1}^{n}\gcd(i,j) \\ & = \sum_{x = 1}^{n}x\sum_{j = 1}^{n}\sum_{i = 1}^{j - 1}[\gcd(i,j) = x] \\ & = \sum_{x = 1}^{n}x\sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor}\sum_{i = 1}^{j = 1}[\gcd(i,j) = 1] \\ & = \sum_{x = 1}^{n}x\sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} \varphi(j) \end{aligned}

到这个时候已经可以 $O(n \sqrt{n})$ 做了，但是我们发现 $n \le 10^6$ ， $O(n \sqrt{n})$ 的复杂度显然过不了。我们发现：一车 $\lfloor \frac{n}{x} \rfloor$ 都是一样的。于是我们直接数论分块。复杂度直接降到 $O(\sqrt{n})$ 。