[题解]CF1900D Small GCD

WaterSun · 2024-04-15 15:49:55 · 题解

更好的阅读体验

拜谢 ssxvngn。

思路

对于 \gcd(a_i,a_j) 的贡献次数为：\sum_{k = j + 1}^{n}[a_k \geq \max(a_i,a_j)]。

因为原式本质是取序列中任意三个元素 a,b,c 做 f 函数，因此与数组是否有序无关，考虑先排序。

那么，上式的贡献就可以写成：n - j。

观察到值域较小，考虑经典转化，将枚举 i,j 转化为枚举 \gcd。

问题转化为求：

发现满足 \gcd(a_i,a_j) = g 的数对，一定满足 g \mid a_i \wedge g \mid a_j \wedge \gcd(\frac{a_i}{g},\frac{a_j}{g}) = 1。

那么问题就转化为了：Link。

枚举 \gcd 时，我们会将数的贡献在 \gcd 的因子时计算一部分。

因此，我们令容斥系数 dp_i = i - \sum_{j \mid i}{dp_j}，然后考虑分别计算一个数与其它数结合，与一个数和自己结合的贡献（同一个数可能会出现多次）。这两种贡献可以通过预处理得到，最后加个和即可。

Code

#include <bits/stdc++.h>
#define re register
#define int long long

using namespace std;

const int N = 1e5 + 10;
int n,arr[N];
int vis[N],sum1[N],sum2[N],dp[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void solve(){
    memset(dp,0,sizeof(dp));
    memset(vis,0,sizeof(vis));
    memset(sum1,0,sizeof(sum1));
    memset(sum2,0,sizeof(sum2));
    int ans = 0;
    n = read();
    for (re int i = 1;i <= n;i++) arr[i] = read();
    sort(arr + 1,arr + n + 1);
    for (re int i = 1;i <= n;i++){
        sum1[arr[i]] += (n - i);
        sum2[arr[i]] += vis[arr[i]] * (n - i);
        vis[arr[i]]++;
    }
    for (re int i = 1;i <= 1e5;i++){
        int cnt = 0,res = 0;
        dp[i] += i;
        for (re int j = i + i;j <= 1e5;j += i) dp[j] -= dp[i];
        for (re int j = i;j <= 1e5;j += i){
            res += cnt * sum1[j] + sum2[j];
            cnt += vis[j];
        }
        ans += dp[i] * res;
    }
    printf("%lld\n",ans);
}

signed main(){
    int T; T = read();
    while (T--) solve();
    return 0;
}