310085: CF1780F. Three Chairs
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Three Chairs
题意翻译
给定一个数组$a_1,a_2,\cdots,a_n$，求满足以下条件的三元组$(a_{k_1},a_{k_2},a_{k_3})$个数： $$ \gcd(\max(a_{k_1},a_{k_2},a_{k_3}), \min(a_{k_1},a_{k_2},a_{k_3}))==1 $$题目描述
One day Kira found $ n $ friends from Morioh and decided to gather them around a table to have a peaceful conversation. The height of friend $ i $ is equal to $ a_i $ . It so happened that the height of each of the friends is unique. Unfortunately, there were only $ 3 $ chairs in Kira's house, and obviously, it will not be possible to seat all friends! So, Kira has to invite only $ 3 $ of his friends. But everything is not so simple! If the heights of the lowest and the tallest of the invited friends are not coprime, then the friends will play tricks on each other, which will greatly anger Kira. Kira became interested, how many ways are there to choose $ 3 $ of his friends so that they don't play tricks? Two ways are considered different if there is a friend invited in one way, but not in the other. Formally, if Kira invites friends $ i $ , $ j $ , and $ k $ , then the following should be true: $ \gcd(\min(a_i, a_j, a_k), \max(a_i, a_j, a_k)) = 1 $ , where $ \gcd(x, y) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of the numbers $ x $ and $ y $ . Kira is not very strong in computer science, so he asks you to count the number of ways to invide friends.输入输出格式
输入格式
The first line contains the number $ n $ ( $ 3 \le n \le 3\cdot10^5 $ ) — the number of Kira's friends. The next line contains $ n $ distinct integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 3\cdot10^5 $ ) — heights of Kira's friends.
输出格式
In a single line output the number of ways to invite three friends.
输入输出样例
输入样例 #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说明
In the first example, only one way is suitable: invite friends $ 1 $ , $ 2 $ , and $ 3 $ . Here $ 1 < 2 < 3 $ , and the numbers $ 1 $ and $ 3 $ are coprime.Input
题意翻译
给定一个数组$a_1,a_2,\cdots,a_n$，求满足以下条件的三元组$(a_{k_1},a_{k_2},a_{k_3})$个数： $$ \gcd(\max(a_{k_1},a_{k_2},a_{k_3}), \min(a_{k_1},a_{k_2},a_{k_3}))==1 $$Output
**题意翻译**
给定一个数组$a_1,a_2,\cdots,a_n$，求满足以下条件的三元组$(a_{k_1},a_{k_2},a_{k_3})$的个数：
$$
\gcd(\max(a_{k_1},a_{k_2},a_{k_3}), \min(a_{k_1},a_{k_2},a_{k_3})) = 1
$$
**题目描述**
有一天，Kira在Morioh找到了$n$个朋友，并决定把他们聚集在一张桌子旁进行和平的交谈。第$i$个朋友的身高是$a_i$。碰巧的是，每个朋友的身高都是独一无二的。
不幸的是，Kira的家里只有3把椅子，显然不可能让所有的朋友都坐下！所以，Kira只能邀请3个朋友。
但事情并非如此简单！如果被邀请的朋友中最高和最矮的朋友的身高不是互质的，那么这些朋友就会互相捉弄，这会大大激怒Kira。
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）](https://en.wikipedia.org/wiki/Greatest_common_divisor)。
Kira在计算机科学方面不是很强**题意翻译** 给定一个数组$a_1,a_2,\cdots,a_n$，求满足以下条件的三元组$(a_{k_1},a_{k_2},a_{k_3})$的个数： $$ \gcd(\max(a_{k_1},a_{k_2},a_{k_3}), \min(a_{k_1},a_{k_2},a_{k_3})) = 1 $$ **题目描述** 有一天，Kira在Morioh找到了$n$个朋友，并决定把他们聚集在一张桌子旁进行和平的交谈。第$i$个朋友的身高是$a_i$。碰巧的是，每个朋友的身高都是独一无二的。 不幸的是，Kira的家里只有3把椅子，显然不可能让所有的朋友都坐下！所以，Kira只能邀请3个朋友。 但事情并非如此简单！如果被邀请的朋友中最高和最矮的朋友的身高不是互质的，那么这些朋友就会互相捉弄，这会大大激怒Kira。 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）](https://en.wikipedia.org/wiki/Greatest_common_divisor)。 Kira在计算机科学方面不是很强
给定一个数组$a_1,a_2,\cdots,a_n$，求满足以下条件的三元组$(a_{k_1},a_{k_2},a_{k_3})$的个数：
$$
\gcd(\max(a_{k_1},a_{k_2},a_{k_3}), \min(a_{k_1},a_{k_2},a_{k_3})) = 1
$$
**题目描述**
有一天，Kira在Morioh找到了$n$个朋友，并决定把他们聚集在一张桌子旁进行和平的交谈。第$i$个朋友的身高是$a_i$。碰巧的是，每个朋友的身高都是独一无二的。
不幸的是，Kira的家里只有3把椅子，显然不可能让所有的朋友都坐下！所以，Kira只能邀请3个朋友。
但事情并非如此简单！如果被邀请的朋友中最高和最矮的朋友的身高不是互质的，那么这些朋友就会互相捉弄，这会大大激怒Kira。
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）](https://en.wikipedia.org/wiki/Greatest_common_divisor)。
Kira在计算机科学方面不是很强**题意翻译** 给定一个数组$a_1,a_2,\cdots,a_n$，求满足以下条件的三元组$(a_{k_1},a_{k_2},a_{k_3})$的个数： $$ \gcd(\max(a_{k_1},a_{k_2},a_{k_3}), \min(a_{k_1},a_{k_2},a_{k_3})) = 1 $$ **题目描述** 有一天，Kira在Morioh找到了$n$个朋友，并决定把他们聚集在一张桌子旁进行和平的交谈。第$i$个朋友的身高是$a_i$。碰巧的是，每个朋友的身高都是独一无二的。 不幸的是，Kira的家里只有3把椅子，显然不可能让所有的朋友都坐下！所以，Kira只能邀请3个朋友。 但事情并非如此简单！如果被邀请的朋友中最高和最矮的朋友的身高不是互质的，那么这些朋友就会互相捉弄，这会大大激怒Kira。 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）](https://en.wikipedia.org/wiki/Greatest_common_divisor)。 Kira在计算机科学方面不是很强