114514

个人认为我的思路是比较自然的。

首先，显然 \(\gcd(a_i,a_j,a_k,a_l) = 1\) 是不好做的，考虑将其转换成总方案数减去 \(\gcd(a_i,a_j,a_k,a_l) \neq 1\) 的方案数。记后半部分为 \(num\)，则原问题等价于求 \(\binom n 4 - num\)。

考虑怎么求 \(num\)，显然有 \(\gcd(a_i,a_j,a_k,a_l) \neq 1\) 等价于 \(\gcd(a_i,a_j,a_k,a_l) = f(f > 1)\)。不妨枚举每个 \(k\), 将所有可以整除它的 \(a_i\) 统计一遍，记作 \(w_i\)，则此时貌似有 \(num = \sum_{i = 2}^{10000} \binom {w_i} 4\)。

但是此时会有重复计算，如 \(\gcd(a_i,a_j,a_k,a_l) = 6\)，则它在 \(2\) 和 \(3\) 都会被统计一遍。考虑容斥，易：

\(num = \binom {w_2} 4 + \binom {w_3} 4 + \binom {w_5} 4 + ... + \binom {w_{prime[tot]}} 4 - \binom {w_{2 \times 3}} 4 - \binom {w_{2 \times 5}} 4 - ...\)

即若 \(i\) 的唯一分解最高次为 \(1\) 且 \(i\) 的唯一分解有 \(c\) 项，则加上 \((-1)^c\binom {w_i} 4\)。将原方程变形，有

\(num = 1\binom {w_{2}} 4 + 1\binom {w_{3}} 4 + 0\binom {w_{4}} 4 + 1\binom {w_{5}} 4 + (-1)\binom {w_{6}} 4 + 1\binom {w_{7}} 4 + 0\binom {w_{8}} 4...\)

由上，不难发现此方程等价于

\(num = \sum_{i = 2}^{10000}[w_i \neq 0]\mu(i)\binom {w_{i}} 4\)

预处理出 \(C\) 与 \(\mu\) 即可。至于 \(w\)，可以用刷表法递推。

总时间复杂度 \(O(T n \log n)\)。

upd:

事实上，该方程有一般形式：

在一个集合 \(a\) 中，记值域上界为 \(k\)，则满足 \(\gcd(b_1, b_2, b_3, ..., b_m) = 1\) 的有序数对方案数为 \(\binom n m - \sum_{i = 2}^{k}[w_i \neq 0]\mu(i)\binom {w_{i}} m\)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 50010;

int C[N], mu[N], p[N], tot;
int w[N], a[N];
bool vis[N];

int n;

void solve(){
	mu[1] = 1;
	for(int i = 2; i <= 10000; i++){
		if(!vis[i]) p[++tot] = i, mu[i] = -1;
		for(int j = 1; j <= tot && i * p[j] <= 10000; j++){
			vis[i * p[j]] = 1;
			if(!(i % p[j])) break;
			mu[i * p[j]] = -mu[i];
		}
	}
	for(int i = 4; i <= 10000; i++){
		C[i] = i * (i - 1) * (i - 2) * (i - 3) / (2 * 3 * 4);
	}
}

signed main(){
	solve();
	while(cin >> n){
		for(int i = 1; i <= n; i++){
			cin >> a[i];w[a[i]]++;
		}
		for(int i = 1; i <= 10000; i++){
			for(int j = i * 2; j <= 10000; j += i){
				w[i] += w[j];
			}
		}
		int ans = 0;
		for(int i = 1; i <= 10000; i++){
			if(w[i] >= 4) ans = ans + C[w[i]] * mu[i];
		}
		cout << ans << endl;
		memset(w, 0, sizeof(w));
	}
	return 0;
}