AT_abc339_f [ABC339F] Product Equality

题目描述

给定 $N$ 个整数 $A_1, A_2, \dots, A_N$。
请计算满足以下条件的整数三元组 $(i, j, k)$ 的个数。

• $1 \leq i, j, k \leq N$
• $A_i \times A_j = A_k$

输入格式

输入以如下格式从标准输入读入。

$N$
$A_1$
$A_2$
$\vdots$
$A_N$

输出格式

请输出满足条件的三元组个数。

输入输出样例 #1

输入 #1

5
2
3
6
12
24

输出 #1

6

输入输出样例 #2

输入 #2

11
1
2
3
4
5
6
123456789123456789
123456789123456789
987654321987654321
987654321987654321
121932631356500531347203169112635269

输出 #2

40

输入输出样例 #3

输入 #3

9
4
4
4
2
2
2
1
1
1

输出 #3

162

说明/提示

限制条件

• $1 \leq N \leq 1000$
• $1 \leq A_i < 10^{1000}$

样例解释 1

满足题目条件的三元组 $(i, j, k)$ 共 $6$ 种，分别为：

• $(1,2,3)$
• $(1,3,4)$
• $(1,4,5)$
• $(2,1,3)$
• $(3,1,4)$
• $(4,1,5)$

样例解释 2

请注意，每个整数 $A_i$ 的值可能非常大。

样例解释 3

请注意，$A_i$ 的值可能存在重复。

由 ChatGPT 4.1 翻译