CF1884D题解

Kreado · 2023-10-22 17:23:32 · 题解

题目传送门。

思路

考虑暴力，首先我们能很容易得到一个 O(n^3) 做法。

现在想想怎么优化到 O(n^2)，我们枚举 i,j，不存在 k 使得 a_{k}\mid a_i 且 a_k\mid a_j，也就是不存在 a_k\mid \gcd(a_i,a_j)。

由于 a_i 值域很小，不妨记 lmx_i 表示数组 a 中是否存在 i 的因子，存在的话，lmx_i=0，否则为 1。

那么现在我们要求的就是 \displaystyle \sum_{i=1}^n \sum_{j=i+1}^n lmx_{\gcd(a_i,a_j)}。

考虑枚举 \gcd，令 p_k 表示数组 a 中有多少组 (i,j) 使得 \gcd(a_i,a_j)=k。

那么得到答案为 \displaystyle \sum_{i=1}^n lmx_i\times p_i。

显然的，对于 lmx_i 我们可以直接根据值域 O(n\ln n) 做，对于 p_i，我们可以按照值域数论容斥做。

数论容斥：令 g_k 表示数组 a 中有多少组 (i,j) 使得 k\mid \gcd(a_i,a_j)。

那么有 p_i=g_i-p_{2i}-p_{3i}-\cdots-p_{ki}(ki\le n)。

直接做即可，时间复杂度 O(n\ln n)。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=1e6+7;
ll T,n,b[Maxn],lmx[Maxn],a[Maxn],ans,p[Maxn];
int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);ans=0;
        for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),b[a[i]]++;

        for(ll i=1;i<=n;i++)
            for(ll j=i;j<=n;j+=i)
                lmx[j]+=b[i];
        for(ll i=n;i;i--){
            for(ll j=i;j<=n;j+=i) p[i]+=b[j];
            p[i]=(p[i]-1)*p[i]/2;
            for(ll j=i<<1;j<=n;j+=i) p[i]-=p[j];

        }
        for(ll i=1;i<=n;i++){
            if(!lmx[i]) ans+=p[i];
        }
        cout<<ans<<endl;
        for(ll i=1;i<=n;i++) b[i]=a[i]=lmx[i]=p[i]=0;
    }
    return 0;
}

当然，我应该做复杂了，也许用不到数论容斥（）