题目简述

给定一个长度为 $n$ 的序列 $a$，问有多少种选出 $4$ 个数使得这四个数的最大公约数为 $1$ 的方案。

题目十分简洁明了，但是难度和题目长度成反比。

正着做十分困难，于是不妨反着做，即用总方案数减去不满足条件的方案数。

易得总方案数为 $C^4_n$。那么接下来考虑怎么算不符合条件的。以下设 $cnt_i$ 表示 $a_1,a_2,\cdots,a_n$ 中含有因数 $i$ 的数的个数。

那么可以发现答案为：
$$ C^4_n+\sum^{n}_{i=1} \mu(i)\times C_{cnt_i}^4 $$

其中 $\mu(i)$ 指莫比乌斯函数。

该式的含义为：总方案数应减去含有 $2,3,5,7,11\cdots$ 这些因数的方案数，但是同时含有两个这些因数的方案会被重复减一次，应加回来。以此类推，可以发现系数正好是 $\mu(i)$。

于是预处理莫比乌斯函数，即可 AC。

代码如下：

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=1e4+5;
int n,ans;
int a[N],miu[N],cnt[N];
bool v[N];

void primes(int n){
    for(int i=1;i<=n;i++){
        miu[i]=1;
    }
    for(int i=2;i<=n;i++){
        if(v[i]) continue;
        miu[i]=-1;
        for(int j=2*i;j<=n;j+=i){
            v[j]=1;
            if((j/i)%i==0) miu[j]=0;
            else miu[j]*=-1;
        }
    }
}

void divide(int n){
    for(int i=1;i*i<=n;i++){
        if(n%i==0){
            cnt[i]++;
            if(i*i!=n) cnt[n/i]++;
        }
    }
}

int C(int n){
    return 1ll*n*(n-1)/2*(n-2)/3*(n-3)/4;
}

signed main(){
    primes(10000);
    while(cin>>n){
        memset(cnt,0,sizeof(cnt));
        int maxn=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            divide(a[i]);
            maxn=max(maxn,a[i]);
        }
        ans=C(n);
        for(int i=2;i<=maxn;i++){
            ans+=miu[i]*C(cnt[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}