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$个。

571 人解决,758 人已尝试。

929 份提交通过,共有 3096 份提交。

2.1 EMB 奖励。

创建: 13 年,9 月前.

修改: 6 年,2 月前.

最后提交: 4 月,1 周前.

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

题目标签