2879. 求三元组个数

单点时限: 2.0 sec

内存限制: 256 MB

有 $n(1 \leqslant n \leqslant 500)$ 个正整数,求由这些整数组成的满足条件的三元组 的个数:$a,b,c$ 两两互质,或 $a,b,c$ 两两不互质。

注意:不考虑 $a,b,c$ 的排列顺序,即 $[a,b,c]$ 与 $[b,a,c]$ 视为同一个三元组。n 个整数可能有重复,不同位置的同一个数不视为相同。

输入格式

第 1 行:一个整数 $n$,表示组成三元组的整数的个数。

第 2 行:由一个空格分隔的 $n$ 个正整数。

输出格式

满足条件的三元组的个数及一个换行符。

样例

Input
6
2 3 5 7 11 13
Output
20

提示

满足条件的三元组包括:
(2,3,5)、(2,3,7)、(2,3,11)、(2,3,13)、(2,5,7)、
(2,5,11)、(2,5,13)、(2,7,11)、(2,7,13)、(2,11,13)、
(3,5,7)、(3,5,11)、(3,5,13)、(3,7,11)、(3,7,13)、
(3,11,13)、(5,7,11)、(5,7,13)、(5,11,13)、(7,11,13)
共$20$个。

730 人解决,924 人已尝试。

1126 份提交通过,共有 3536 份提交。

1.7 EMB 奖励。

创建: 15 年,6 月前.

修改: 8 年前.

最后提交: 1 月前.

来源: 编程实践第4次考试

题目标签