CF1822G2 Magic Triples (Hard Version)

这是该问题的困难版本。唯一的区别在于本版本中 $a_i \le 10^9$。 给定一个长度为 $n$ 的整数序列 $a$，如果三元组 $(i, j, k)$ 满足以下条件，则称其为“magic 三元组”： - $1 \le i, j, k \le n$。 - $i$、$j$、$k$ 两两不同。 - 存在一个正整数 $b$，使得 $a_i \cdot b = a_j$ 且 $a_j \cdot b = a_k$。 Kolya 收到了一份整数序列 $a$ 作为礼物，现在他想统计其中 magic 三元组的数量。请你帮助他完成这个任务！ 注意，$i$、$j$、$k$ 的顺序没有任何限制。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$），表示序列的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, a_3, \dots, a_n$（$1 \le a_i \le 10^9$），表示序列 $a$ 的元素。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示该序列中 magic 三元组的数量。

在第一个样例中，序列 $a$ 有 $6$ 个 magic 三元组，分别是 $(2, 3, 5)$、$(2, 5, 3)$、$(3, 2, 5)$、$(3, 5, 2)$、$(5, 2, 3)$、$(5, 3, 2)$。 在第二个样例中，序列 $a$ 只有一个 magic 三元组 $(2, 1, 3)$。 由 ChatGPT 4.1 翻译