Link

CF1884 D Counting Rhyme

Question

给定长度为 \(n\) 的数组 \(a\) 如果两个不同的下标 \(a_i,a_j\) 不能被任意一个元素 \(a_k,(1 \le k \le n)\) 共同整除，那么说明 \((i,j)\) 是"好对" ，求"好对" 的个数

Solution

定义 \(g[i]\) 表示当因子为 \(i\) 的元素对的个数

如果有 \(s\) 个数能整除 \(g[i]\) 那么 \(g[i] = C_s^2\) ，但是我们发现会把公约数为 \(i\) 的倍数也一起算进去，所以要减掉，所以

\[g[i] = C_s^2 - \sum{g[i \times j]} \]

考虑答案，如果数组中某个元素 \(x\) 能整除 \(i\) 那么 \(g[i]\) 不可取

所以我们只需要用一个 \(vis[]\) 来标记那些数没有被某个元素整除，然后求和就好了

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2e6+5;
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;
}
LL C(LL x){
    return (x)*(x-1)>>1;
}
int N,vis[maxn];
LL ans,num,g[maxn],a[maxn],hsh[maxn],Max;
//g[i] 表示数字为 i 的时候，gcd(,) = i 的个数

int main(){
    // freopen("D.in","r",stdin);
    // freopen("D.out","w",stdout);
    int T=read();
    while(T--){
        ans=0;
        N=read();
        for(int i=1;i<=N;i++) vis[i]=hsh[i]=g[i]=0;
        for(int i=1;i<=N;i++)a[i]=read(),hsh[a[i]]++;
        Max=N;
        for(int i=Max;i;i--){
            num=0;
            for(int j=1;j*i<=Max;j++){
                num+=hsh[j*i];
            }
            g[i]+=C(num);
            for(int j=2;j*i<=Max;j++){
                g[i]-=g[i*j];
            }
        }
        for(int i=1;i<=Max;i++)if(hsh[i]){
            for(int j=1;j*i<=Max;j++)
                vis[i*j]=1;
        }
        for(int i=1;i<=Max;i++) 
            if(!vis[i])
                ans+=g[i];
        printf("%lld\n",ans);
    }
    return 0;
}