\(\sum\sum gcd(i,j) \times gcd(a_i,a_j)\)
考虑枚举这个 \(gcd(i,j)\) 。
\(\sum_d \varphi(d)\sum_{i|d}\sum_{j|d} gcd(a_i,a_j)\)
考虑后者等同于计算\(\sum_i\sum_j gcd(a_i,a_j)\)
我们考虑枚举约数 \(d\)，那么会 \(d | gcd\) 的情况为 \((\sum[d | a_i]) ^ 2\)
考虑我们要求的是最大公约数，而非约数。
但是我们有\(x = \sum_{d|x}\varphi(x)\)
我们在情况数前加上一个系数即可。
转而求
\(\sum_d \varphi(d)\sum_t \varphi(t) (\sum[t | a_{k * d}]) ^ 2\)
那么预处理出因数，我们枚举 \(d\) ，然后 \(O(nln)\) 的遍历 \(a_i\) ，然后一次 \(d(n)\) 的处理一个数。
那么复杂度为预处理\(O(nln)\)，计数复杂度\(O(\sum \lfloor\frac{n}{i} \rfloor d(i)) \leq O(Max{d(u)}nln)\)
#include
#include
#include