解决本题的核心在于利用莫比乌斯反演或容斥原理，将“最大公约数（\(\gcd\)）等于 1”的限制转化为“统计倍数个数”。
核心思路
直接统计 \(\gcd(a_i, a_j, a_k, a_l) = 1\) 的四元组非常困难，因此我们采用莫比乌斯反演进行转化：
根据莫比乌斯函数的性质：\(\sum_{d|n} \mu(d) = [n=1]\)。
我们可以将要求的答案表示为：
\[\text{Ans} = \sum_{i,j,k,l} [\gcd(a_i, a_j, a_k, a_l) = 1] = \sum_{i,j,k,l}\ \sum_{d | \gcd(a_i, a_j, a_k, a_l)} \mu(d)
\]
交换求和符号，先枚举因数 \(d\)：
\[\text{Ans} = \sum_{d=1}^{\max(a)} \mu(d) \cdot \text{计算从序列中选出 4 个数全为 } d \text{ 的倍数的方案数}
\]
设 \(f(d)\) 为输入序列中 \(d\) 的倍数 的元素个数。那么在这些倍数中任意挑选 4 个数组成四元组的方案数就是组合数 \(\binom{f(d)}{4}\)。因此，最终的计算公式为：
\[\text{Ans} = \sum_{d=1}^{\max(a)} \mu(d) \cdot \binom{f(d)}{4}
\]
具体算法步骤
- 预处理莫比乌斯函数 \(\mu\)：用线性筛求出 \(1\) 到值域最大值 \(\max(a)\) 之间所有数的 \(\mu(d)\) 值。
- 计数频次：用一个桶数组
cnt[x]统计每个数字在输入序列中出现的次数。 - 计算 \(f(d)\)：通过调和级数复杂度的循环来统计 \(d\) 的倍数个数。即 \(f(d) = \sum_{d \mid x} cnt[x]\)，时间复杂度为 \(O(M \log M)\)，其中 \(M = \max(a)\)。
- 累加贡献：遍历所有的 \(d\)，如果 \(f(d) \ge 4\)，则计算组合数并将 \(\mu(d) \cdot \binom{f(d)}{4}\) 累加到答案中。
示例程序
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e4, maxn = N + 5;bool isp[maxn];
int n, mu[maxn], c[maxn], C[maxn];void init() {vector<int> primes;mu[1] = 1;for (int i = 2; i <= N; i++) {if (!isp[i]) {primes.push_back(i);mu[i] = -1;}for (auto &j : primes) {if (i * j > N) break;isp[i * j] = true;if (i % j == 0) {mu[i * j] = 0;break;}else {mu[i * j] = mu[i] * (-1);}}}
}ll f(int a) {if (a < 4) return 0;return 1ll * a * (a-1) * (a-2) * (a-3) / (4 * 3 * 2);
}int main() {init();while (~scanf("%d", &n)) {memset(c, 0, sizeof c);memset(C, 0, sizeof C);for (int i = 0, a; i < n; i++) {scanf("%d", &a);c[a]++;}for (int i = 1; i <= N; i++) {for (int j = i; j <= N; j += i)C[i] += c[j];}ll ans = 0;for (int i = 1; i <= N; i++)ans += mu[i] * f(C[i]);printf("%lld\n", ans);}return 0;
}