310367: CF1822G1. Magic Triples (Easy Version)
Description
This is the easy version of the problem. The only difference is that in this version, $a_i \le 10^6$.
For a given sequence of $n$ integers $a$, a triple $(i, j, k)$ is called magic if:
- $1 \le i, j, k \le n$.
- $i$, $j$, $k$ are pairwise distinct.
- there exists a positive integer $b$ such that $a_i \cdot b = a_j$ and $a_j \cdot b = a_k$.
Kolya received a sequence of integers $a$ as a gift and now wants to count the number of magic triples for it. Help him with this task!
Note that there are no constraints on the order of integers $i$, $j$ and $k$.
InputThe first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
The first line of the test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the length of the sequence.
The second line of the test contains $n$ integers $a_1, a_2, a_3, \dots, a_n$ ($1 \le a_i \le 10^6$) — the elements of the sequence $a$.
The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
OutputFor each test case, output a single integer — the number of magic triples for the sequence $a$.
ExampleInput7 5 1 7 7 2 7 3 6 2 18 9 1 2 3 4 5 6 7 8 9 4 1000 993 986 179 7 1 10 100 1000 10000 100000 1000000 8 1 1 2 2 4 4 8 8 9 1 1 1 2 2 2 4 4 4Output
6 1 3 0 9 16 45Note
In the first example, there are $6$ magic triples for the sequence $a$ — $(2, 3, 5)$, $(2, 5, 3)$, $(3, 2, 5)$, $(3, 5, 2)$, $(5, 2, 3)$, $(5, 3, 2)$.
In the second example, there is a single magic triple for the sequence $a$ — $(2, 1, 3)$.
Input
题意翻译
有 $t$ 组数据,每组数据给定一个长为 $n$ 的序列 $a$ 求能选出多少个 $i,j,k$ 使得 $a_i \times b=a_j , a_j \times b=a_k$ $b$是一个自定数,对于每组 $i,j,k$ 都可以不相同Output
这个题目是“神奇三元组”问题的简单版本。在这个版本中,序列中的每个整数a_i都满足a_i ≤ 10^6。对于一个给定的整数序列a,一个三元组(i, j, k)被称为“神奇”的,如果满足以下条件:
1. 1 ≤ i, j, k ≤ n。
2. i, j, k两两不同。
3. 存在一个正整数b,使得a_i * b = a_j和a_j * b = a_k。
Kolya收到了一个整数序列a作为礼物,并想要计算这个序列的“神奇三元组”的数量。帮助他完成这个任务!
注意,整数i, j和k的顺序没有限制。
输入输出数据格式:
输入:
- 第一行包含一个整数t(1 ≤ t ≤ 10^4),表示测试用例的数量。
- 每个测试用例的描述如下:
- 第一行包含一个整数n(3 ≤ n ≤ 2 * 10^5),表示序列的长度。
- 第二行包含n个整数a_1, a_2, a_3, ..., a_n(1 ≤ a_i ≤ 10^6),表示序列a的元素。
- 所有测试用例的n之和不超过2 * 10^5。
输出:
- 对于每个测试用例,输出一个整数,表示序列a的“神奇三元组”的数量。
示例:
输入:
```
7
5
1 7 7 2 7
3
6 2 18
9
1 2 3 4 5 6 7 8 9
4
1000 993 986 179
7
1 10 100 1000 10000 100000 1000000
8
1 1 2 2 4 4 8 8
9
1 1 1 2 2 2 4 4 4
```
输出:
```
6
1
3
0
9
16
45
```题目大意: 这个题目是“神奇三元组”问题的简单版本。在这个版本中,序列中的每个整数a_i都满足a_i ≤ 10^6。对于一个给定的整数序列a,一个三元组(i, j, k)被称为“神奇”的,如果满足以下条件: 1. 1 ≤ i, j, k ≤ n。 2. i, j, k两两不同。 3. 存在一个正整数b,使得a_i * b = a_j和a_j * b = a_k。 Kolya收到了一个整数序列a作为礼物,并想要计算这个序列的“神奇三元组”的数量。帮助他完成这个任务! 注意,整数i, j和k的顺序没有限制。 输入输出数据格式: 输入: - 第一行包含一个整数t(1 ≤ t ≤ 10^4),表示测试用例的数量。 - 每个测试用例的描述如下: - 第一行包含一个整数n(3 ≤ n ≤ 2 * 10^5),表示序列的长度。 - 第二行包含n个整数a_1, a_2, a_3, ..., a_n(1 ≤ a_i ≤ 10^6),表示序列a的元素。 - 所有测试用例的n之和不超过2 * 10^5。 输出: - 对于每个测试用例,输出一个整数,表示序列a的“神奇三元组”的数量。 示例: 输入: ``` 7 5 1 7 7 2 7 3 6 2 18 9 1 2 3 4 5 6 7 8 9 4 1000 993 986 179 7 1 10 100 1000 10000 100000 1000000 8 1 1 2 2 4 4 8 8 9 1 1 1 2 2 2 4 4 4 ``` 输出: ``` 6 1 3 0 9 16 45 ```