四元组最大公约数为1

题目描述

给定你一个由 $N$ 个不同整数构成的整数序列，从这个整数序列中选出 $4$ 个数，使得这 $4$ 个数的唯一公约数为 $1$。

求满足条件的四元组的个数。

输入格式

输入中包含多组测试用例。

每个测试用例占据两行：

• 第一行包含整数 $N$
• 第二行包含 $N$ 个用空格隔开的整数（均不超过 $10000$），表示完整的整数序列

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

$1 \le N \le 10000$

输入样例

4
2 3 4 5 
4
2 4 6 8 
7
2 3 4 5 7 6 8

输出样例

1 
0 
34

样例解释

第一个测试用例：N=4，序列 [2, 3, 4, 5]

从4个数中选4个数只有1种选法：{2, 3, 4, 5}

计算这4个数的最大公约数：

• $\gcd(2,3,4,5) = 1$

满足条件，所以有1个四元组。

输出：1

第二个测试用例：N=4，序列 [2, 4, 6, 8]

从4个数中选4个数：{2, 4, 6, 8}

计算最大公约数：

• $\gcd(2,4,6,8) = 2 \neq 1$

不满足条件，所以有0个四元组。

输出：0

第三个测试用例：N=7，序列 [2, 3, 4, 5, 7, 6, 8]

总共有 $C(7,4) = 35$ 种四元组。

需要统计其中最大公约数为1的有多少个。

计算结果为34个（只有1个四元组的最大公约数不为1）。

输出：34

问题分析

直接暴力法不可行

从 $N$ 个数中选 $4$ 个的组合数为 $C(N,4)$，当 $N=10000$ 时：

$$C(10000,4) = \frac{10000 \times 9999 \times 9998 \times 9997}{24} \approx 4.17 \times 10^{15}$$

显然不能枚举所有四元组。

转化为容斥原理

设：

• $f(d)$ = 最大公约数正好为 $d$ 的四元组个数
• $g(d)$ = 最大公约数是 $d$ 的倍数的四元组个数

那么：

$$g(d) = \sum_{d|m} f(m)$$

根据莫比乌斯反演：

$$f(d) = \sum_{d|m} \mu\left(\frac{m}{d}\right) g(m)$$

我们要求的是 $f(1)$：

$$f(1) = \sum_{m=1}^{M} \mu(m) g(m)$$

其中 $M$ 是序列中最大数的最大值（不超过10000）。

计算 $g(m)$

$g(m)$ 表示最大公约数是 $m$ 的倍数的四元组个数。

如何计算？我们需要知道序列中有多少个数是 $m$ 的倍数。

设 $cnt[m]$ = 序列中是 $m$ 的倍数的数的个数。

那么从这些数中任选4个，它们的最大公约数一定是 $m$ 的倍数（但不一定是正好 $m$，可能是 $m$ 的更大倍数）。

所以：

$$g(m) = C(cnt[m], 4)$$

即从 $cnt[m]$ 个数中选4个的组合数。

计算 $cnt[m]$

对于序列中的每个数 $a_i$，枚举 $a_i$ 的所有约数 $d$，然后 $cnt[d]++$。

由于 $a_i \le 10000$，每个数的约数个数最多约 $100$ 个，所以总复杂度为 $O(N \cdot \sqrt{M})$，可以接受。

莫比乌斯函数 $\mu(m)$

需要预先计算 $\mu(1)$ 到 $\mu(M)$，可以使用线性筛法。

算法步骤

对于每个测试用例：

1. 初始化：

   • 读取 $N$ 和序列
   • 确定最大值 $M = \max(a_i)$
   • 初始化 $cnt$ 数组全为0

2. 统计 $cnt[m]$：

   • 对于每个数 $a_i$，枚举它的所有约数 $d$
   • $cnt[d]++$

3. 计算 $g(m)$：

   • 对于 $m = 1$ 到 $M$，$g(m) = C(cnt[m], 4)$
   • 组合数可以用公式计算：$C(n,4) = \frac{n(n-1)(n-2)(n-3)}{24}$

4. 计算 $f(1)$：

   • 预处理莫比乌斯函数 $\mu(m)$
   • $f(1) = \sum_{m=1}^{M} \mu(m) \cdot g(m)$

5. 输出结果

示例详细计算

第一个测试用例：N=4，序列 [2, 3, 4, 5]

最大值 $M=5$

步骤1：统计 $cnt[m]$

• 2的约数：1,2 → cnt[1]++, cnt[2]++
• 3的约数：1,3 → cnt[1]++, cnt[3]++
• 4的约数：1,2,4 → cnt[1]++, cnt[2]++, cnt[4]++
• 5的约数：1,5 → cnt[1]++, cnt[5]++

结果：

• cnt[1] = 4
• cnt[2] = 2
• cnt[3] = 1
• cnt[4] = 1
• cnt[5] = 1
• 其他 cnt[m] = 0

步骤2：计算 $g(m)$

• g(1) = C(4,4) = 1
• g(2) = C(2,4) = 0（因为2<4）
• g(3) = C(1,4) = 0
• g(4) = C(1,4) = 0
• g(5) = C(1,4) = 0

步骤3：计算 $f(1)$ 莫比乌斯函数：

• μ(1) = 1
• μ(2) = -1
• μ(3) = -1
• μ(4) = 0（4有平方因子2²）
• μ(5) = -1

$$f(1) = \mu(1)g(1) + \mu(2)g(2) + \mu(3)g(3) + \mu(4)g(4) + \mu(5)g(5) = 1 \times 1 + (-1) \times 0 + (-1) \times 0 + 0 \times 0 + (-1) \times 0 = 1$$

输出：1

时间复杂度

1. 统计 $cnt[m]$：$O(N \cdot \sqrt{M})$，其中 $M \le 10000$
2. 计算 $g(m)$ 和 $f(1)$：$O(M)$
3. 总复杂度：$O(N \sqrt{M} + M)$，可以接受

注意事项

1. 序列中的数各不相同
2. 使用 long long 存储结果，因为结果可能很大
3. 组合数计算时注意整数溢出
4. 莫比乌斯函数需要预处理到 $M=10000$

莫比乌斯函数计算

使用线性筛：

• μ(1) = 1
• 对于质数 p：μ(p) = -1
• 如果数 n 有平方因子：μ(n) = 0
• 否则：μ(n) = (-1)^k，其中 k 是 n 的不同质因数个数

时空限制

• 时间限制：1秒
• 空间限制：64MB