题目链接：https://codeforces.com/contest/1900/problem/D
对于已经排序好的数组 \(a\)，我们需要计算：
\[\sum_{i=1}^n\sum_{j=i+1}^n gcd(a_i, a_j) * (n - j) \]由于 \(\sum_{d|n} \phi(d) = n\)，因此：
\[\gcd(a_i, a_j) = \sum_{d|a_i, d|a_j} \psi(d) \]代入可得：
\[\sum_{i=1}^n\sum_{j=i+1}^n\sum_{d|a_i, d|a_j} \psi(d) \cdot (n - j) \]因此，枚举到 \(a_j\) 时，遍历它的每个因数 \(d\)，看之前有多少个 \(a_i\) 有因数 \(d\)，乘上 \(\psi(d) \cdot (n-j)\) 即可。
求多个数欧拉函数的方法有很多，可以用埃筛或者线性筛。
埃筛递推思路：对于每个质数 \(p\)，把它的倍数都乘上 \((p - 1) / p\) 即可。
线性筛递推思路，对于质数 \(p\) 有：
- 若 \(p\) 是 \(n\) 的因子，但 \(p^2\) 不是 \(n\) 的因子，那么 \(\psi(n) = \psi(n / p) \cdot p\)
- 若 \(p\) 是 \(n\) 的因子，并且 \(p^2\) 也是 \(n\) 的因子，那么 \(\psi(n) = \psi(n / p) \cdot (p - 1)\)
那么，如果用上 \(\sum_{d|n} \phi(d) = n\) 这条结论，可以得出 \(\psi(n) = n - \sum_{d|n,d\neq n} \psi(d)\)。这样也可以在 \(O(n\log n)\) 的复杂度来求欧拉函数，并且代码更好记也更好写。
除此以外，由于 \(10^5\) 以内的数字最多有 128 个因数，因此可以先遍历存下所有数字的因数。总体时间复杂度为 \(O(m\log m)\)。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> phi;
vector<vector<int>> fac;
vector<int> getPhi(int n) {
vector<int> f(n + 1);
for (int i = 1; i <= n; i++) {
f[i] = i;
}
for (int i = 1; i <= n; i++) {
fac[i].push_back(i);
for (int j = 2 * i; j <= n; j += i) {
f[j] -= f[i];
fac[j].push_back(i);
}
}
return f;
}
vector<int> getPhi1(int n) {
vector<int> f(n + 1);
for (int i = 1; i <= n; i++) {
f[i] = i;
fac[i].push_back(1);
}
for (int i = 2; i <= n; i++) {
if (f[i] == i) {
for (int j = i; j <= n; j += i) {
f[j] = f[j] / i * (i - 1);
}
}
for (int j = i; j <= n; j += i) {
fac[j].push_back(i);
}
}
return f;
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
unordered_map<int, int> mp;
ll res = 0;
for (int i = 0; i < n; i++) {
for (int x : fac[a[i]]) {
res += 1ll * mp[x] * phi[x] * (n - i - 1);
mp[x]++;
}
}
cout << res << "\n";
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
int n = 1e5;
fac.resize(n + 1);
phi = getPhi(n);
while (T--) {
solve();
}
}