B-小苯的三元组_2024年中国传媒大学程序设计大赛（同步赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小苯给了你一个数组 $a$ ，他想知道数组中有多少个三元组 $(i, j, k)$ ，满足 $lcm(a_i, a_j) \leq gcd(a_j, a_k)$ 。

其中：

$gcd(x, y)$ 表示 $x, y$ 的最大公约数。

$lcm(x, y)$ 表示 $x, y$ 的最小公倍数。

注：小苯认为， $(x_1, x_2, x_3)$ 和 $(y_1, y_2, y_3)$ 两个三元组不同，当且仅当至少存在一个 $i, (1 \leq i \leq 3)$ 使得 $(x_i \ne y_i)$ 。

输入包含两行。
第一行一个正整数 ，表示数组  的长度。
第二行  个正整数  表示数组的元素。

输出包含一行一个正整数，表示三元组的个数。

示例1

复制

3
1 2 3

复制

, , , , , ,

示例2

复制

5
5 6 3 1 9

复制

示例3

复制

3
1 1 1

复制