Link

CF1900 D Small GCD

Question

定义 \(f(x,y,z)=\gcd(a,b)\) ，其中 \(a,b\) 为 \(x,y,z\) 中较小的那两个数

给出数组 \(a\)，求

\[\sum\limits_{i=1}^n \sum\limits_{j=i+1}^n \sum\limits_{k=j+1}^n f(a_i,a_j,a_k) \]

三个求和符号本质上就是选数组 \(a\) 中的三个数，也就是说，数组的排列顺序其实是无关的，所以把数组 \(a\) 从小到大排序后再处理这个问题

排序后，\(a_k\) 肯定是最小的，所以答案就变成了

\[\sum\limits_{i=1}^n \sum\limits_{j=i+1}^n \gcd(a_i,a_j) \times (n-i) \]

再优化以下式子，固定住 \(a_j\) 不动

\[\sum\limits_{j=2}^n \sum\limits_{i=1}^{j-1} \gcd(a_i,a_j) \times (n-i) \]

我们单独看每一个 \(a_j\) ，设 \(x=a_j\) 问题就转化为求

\[\sum\limits_{i=1}^{j-1} \gcd(a_i,x) \]

考虑到 \(a_i\) 的范围特别小，可以枚举 \(x\) 的所有因子 \(y\) 计算 \(\gcd(x,a_i)=y\) 的 \(a_i\) 有多少个

定义 \(cnt_y\) 表示当前满足 \(a_i=y\) 的倍数的 \(i\) 有多少个

例如 \(x=16,y=4\) 那么 \(a_i=4,8,12,16\) 满足

但是我们发现这样子会把 \(\gcd()=8,12,16\) 的都算进去，所以考虑容斥，需要减掉

例如 \(x=16,a_i=8\) 在 \(y=8\) 的时候算了一次，在 \(y=4\) 的时候又算了一次

定义 \(F_y\) 表示 \(\gcd(x,a_i)=y\) 的 \(a_i\) 的数量，有 \(F_y=cnt_y-\sum\limits_{k=2} F_{ky}\)

具体实现时，在每次计算出 \(F_y\) 后，对其因子减去其贡献

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

const int maxn=1e5+5;
int N;
vector<int> factor[maxn];

void solve(){
    LL ans=0;
    N=read();
    vector<int> cnt(maxn+1);
    vector<LL> f(maxn+1);
    vector<int> a;
    for(int i=1;i<=N;i++) 
        a.push_back(read());
    sort(a.begin(),a.end());
    for(int i=0;i<N;i++){
        LL now=0;
        int x=a[i];
        for(int k=factor[x].size()-1;k>=0;k--){
            int t=factor[x][k];
            f[t]+=cnt[t];
            now+=t*f[t];
            for(auto tt:factor[t])
                f[tt]-=f[t];
        }
        for(auto t:factor[x]){
            cnt[t]+=1;
            f[t]=0;
        }
        ans+=now*(N-i-1);
    }
    cout<<ans<<'\n';
    return ;
}

int main(){
	cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    for(int i=1;i<maxn;i++)
        for(int j=i;j<maxn;j+=i)
            factor[j].push_back(i);
    int T=read();
    while(T--) solve();
}