← 返回题目列表

Codeforces · 1780/F

F. 三把椅子

中文机器翻译题面 查看原题

有一天,Kira 找到了来自 Morioh 的 $$$n$$$ 朋友,并决定将他们聚集在一张桌子旁进行和平对话。好友 $$$i$$$ 的身高等于 $$$a_i$$$。碰巧的是,每个朋友的身高都是独一无二的。

不幸的是,Kira 家里只有 $$$3$$$ 椅子,显然不可能让所有朋友都坐下!因此,Kira 仅需邀请 $$$3$$$ 的朋友。

但是一切并没有那么简单!如果邀请的朋友中最低的和最高的身高不互质,那么朋友们就会互相捉弄,这会极大地激怒基拉。

Kira开始感兴趣了,有多少种方法可以选择他的朋友$$$3$$$,这样他们就不会耍花招了?如果有朋友以一种方式被邀请,但没有以另一种方式被邀请,则两种方式被认为是不同的。

正式来说,如果 Kira 邀请好友 $$$i$$$、$$$j$$$ 和 $$$k$$$,则应满足以下条件:$$$\gcd(\min(a_i, a_j, a_k), \max(a_i, a_j, a_k)) = 1$$$,其中 $$$\gcd(x, y)$$$ 表示数字 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

Kira 的计算机科学不是很强,所以他要求你数一下邀请好友的方式。

输入

第一行包含数字 $$$n$$$ ($$$3 \le n \le 3\cdot10^5$$$) — Kira 的朋友数量。

下一行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 3\cdot10^5$$$) — Kira 朋友的身高。

输出

在一行中输出邀请三位好友的方法数量。

示例

输入 #1

3
1 2 3

输出 #1

1

输入 #2

4
1 6 2 3

输出 #2

3

输入 #3

4
16 4 8 2

输出 #3

0

输入#4

10
10 1 6 7 9 8 4 3 5 2

输出#4

77

注意

在第一个示例中,只有一种方式适合:邀请好友 $$$1$$$、$$$2$$$ 和 $$$3$$$。这里 $$$1 < 2 < 3$$$,数字 $$$1$$$ 和 $$$3$$$ 是互质的。