← 返回题目列表

AtCoder · abc339_f

I. 产品平等

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

你被给予 N 整数 A_1, A_2, \dots, A_N.
求整数三元组的个数 (i, j, k) 满足以下条件:

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

约束

  • 1 \le N \le 1000
  • \color{red}{1 \le A_i < 10^{1000}}

输入

输入由标准输入按以下格式给出:

N
A_1
A_2
\vdots
A_N

输出

将答案打印为整数。


示例输入 1

5
2
3
6
12
24

示例输出 1

6

以下六个三元组 (i, j, k) 满足问题陈述中的条件:

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

示例输入 2

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

示例输出 2

40

请注意每个整数的值 A_i 可能很大。


示例输入 3

9
4
4
4
2
2
2
1
1
1

示例输出 3

162

请注意,以下值之间可能存在重复 A_i.