题解 UVA11424 GCD - Extreme (I)

Description

\[\sum_{i = 1}^{n} \sum_{j = i + 1}^{n} \gcd(i, j) \]

Solution

莫反练习题。

我们知道 \(id(n) = n\) ，所以原式化为：

\[\sum_{i = 1}^{n} \sum_{j = i + 1}^{n} id(\gcd(i,j)) \]

又因为 $id = \varphi \ast I $， 那么：

\[\begin{aligned} id(n) & = \sum_{d \mid n} \varphi(d) \times I(\frac{n}{d}) \\ & = \sum_{d \mid n} \varphi(d) \end{aligned} \]

所以上式化为：

\[\sum_{i = 1}^{n} \sum_{j = i + 1}^{n} \sum_{d \mid \gcd(i,j)} \varphi (d) \]

把 \(d\) 提到前面去，\(i,j\) 改为枚举 \(d\) 的倍数。

\[\sum_{d = 1}^{n} \sum_{i = 1}^{\left \lfloor \frac{n}{d} \right \rfloor} \sum_{j = i + 1}^{\left \lfloor \frac{n}{d} \right \rfloor} \varphi (d) \]

后面的变量与后面两个 \(\sum\) 中的变量无关，可以直接化掉。不同于其他大佬的做法，我们先把这两个 \(\sum\) 拿出来，并设 \(x = {\left \lfloor \frac{n}{d} \right \rfloor}\) 。两个 \(\sum\) 变成：

\[\sum_{i = 1}^{x} \sum_{j = i + 1}^{x} 1 = \frac{x (x-1)}{2} \]

所以不用在减去重复的并除以 \(2\)，直接代回去可得：

\[\sum_{d = 1}^{n} \frac{x(x-1)}{2} \varphi(d) \]

枚举 \(d\) 即可，复杂度 \(O(n)\)。

考虑到有多组数据，只是 \(O(n)\) 的枚举还是会 T 掉，所以使用整除分块优化。

不会的话可以看一下这位大佬的博客 ->

整除分块的复杂度为 \(O(\sqrt{n})\)，总复杂度为 \(O(T\sqrt{n})\)，其中 \(T\) 表示有 \(T\) 组数据。

剩下的看代码吧。

Code

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#define LL long long
#define orz cout<<"lkp AK IOI!"<