526互联

Codeforces Round 911 (Div. 2)

发布时间 2023-11-28 02:27:47作者: bible_w

Codeforces Round 911 (Div. 2)

D - Small GCD

思路：求Σf（ai，aj，ak），其实就是所有gcd（ai，aj）的贡献，那么ijk的顺序就不重要了，首先可以将a排序。

可以枚举j，求出Σgcd（ai，aj），i<j，且k的个数等于Σgcd（ai，aj）贡献的次数，那么答案就是Σgcd（ai，aj）*（n-i），i<j

考虑到复杂度，怎么求Σgcd（ai，aj），i<j 呢？

 

引入欧拉反演

 

 

 

 

 

n/d表示n以内的数中为d的倍数的数量，在本题中可以维护a1~ai的所有数中d的倍数的数量cnt[d]

则有

 

 

 

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
int cnt,primes[N],phi[N];
bool st[N];
int n;
void get_phi(int n){
    phi[1]=1;
    for(int i=2;i<=n;++i){
        if(!st[i])phi[i]=i-1,primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;++j){
            int t=i*primes[j];
            st[t]=true;
            if(i%primes[j]==0){
                phi[t]=phi[i]*primes[j];
                break;
            }
            else phi[t]=phi[i]*(primes[j]-1);
        }
    }
}

void solve(){
    cin>>n;
    vector<int>a(n+1),num(N);
    for(int i=1;i<=n;++i)cin>>a[i];
    sort(a.begin()+1,a.end());
    int ans=0;
    for(int i=1;i<n;++i){
        int s=0,x=a[i];
        for(int j=1;j*j<=x;++j){
            if(x%j)continue;
            s+=phi[j]*num[j]++;
            if(j*j!=x)s+=phi[x/j]*num[x/j]++;
        }
        ans+=s*(n-i);
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    get_phi(100000);
    while(t--){
        solve();
    }
    return 0;
}
View Code