Codeforces Round 911 (Div. 2) D

D. Small GCD

题意

给定数组 \(a\) ,求出数组 \(a\) 中所有三元组中较小的两个元素的 \(gcd\) 的和.

分析

显然数组中元素的顺序不影响统计答案，为了方便先将数组排个序；
枚举中间的元素 \(a_j\) ,那么只有它前边的元素能与其产生贡献，它后边的元素个数就是这个贡献的倍数，下面考虑枚举中间元素时的贡献
所求即为 \(\sum\limits_{i=1}^{j-1}{gcd\left(a_i,a_j\right)}\) , 无论怎样的暴力都是 \(n^2\) 的。
赛时没想出来优化，赛后看了别人代码才想到欧拉反演。

欧拉反演公式：\(n = \sum\limits_{d\mid n}{\phi \left(n\right)}\)
证明欧拉反演的话只要证明因子的的欧拉函数之和是一个积性函数就能顺利整出来。

有了上述结论，原式子可以转为 \(\sum\limits_{i=1}^{j-1}\sum\limits_{d\mid\left(a_i,a_j\right)}{\phi \left(d\right)}\)
已经是一个易处理的柿子，考虑实现细节
从前往后枚举元素，假设已经处理到了 \(a_j\) ,枚举因子 \(x\) ，如果前面 \(j - 1\) 个元素中已经出现了 \(cnt\) 次因子 \(x\) ，那么这一位的贡献直接加上 \(cnt * \phi(x)\), 同时++cnt;
最后给每一位贡献乘上系数即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL),cout.tie(NULL)
const int N = 1e5 + 7;
int phi[N];
void init(int n){
    for (int i(1); i <= n; ++i) phi[i] = i;
    for (int i(1); i <= n; ++i)
        for (int j(2 * i); j <= n; j += i)
            phi[j] -= phi[i];
}

void doit(){
    int n; cin >> n;
    vector<int> a(n + 1), cnt(N);
    for (int i(1); i <= n; ++i) cin >> a[i];
    sort(a.begin() + 1, a.end());

    ll ans = 0;

    for (int i(1); i <= n; ++i){
        int x = a[i];
        ll res = 0;
        for (int j(1); j * j <= x; ++j){
            if (x % j) continue;
            res += 1ll * phi[j] * cnt[j]++;
            if (j * j != x) res += 1ll * phi[x / j] * cnt[x / j]++;
        }
        ans += res * (n - i);
    }

    cout << ans << '\n';

}

int main(){
    IOS;
    //freopen("in.txt", "r", stdin);
    int T = 1; cin >> T;
    init(N);
    while (T--){
        doit();
    }
    return 0;
}