103395: [Atcoder]ABC339 F - Product Equality
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:3
Solved:0
Description
Score: $550$ points
Problem Statement
You are given $N$ integers $A_1, A_2, \dots, A_N$.
Find the number of triples of integers $(i, j, k)$ that satisfy the following conditions:
- $1 \le i, j, k \le N$
- $A_i \times A_j = A_k$
Constraints
- $1 \le N \le 1000$
- $\color{red}{1 \le A_i < 10^{1000}}$
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\vdots$ $A_N$
Output
Print the answer as an integer.
Sample Input 1
5 2 3 6 12 24
Sample Output 1
6
The following six triples $(i, j, k)$ satisfy the conditions in the problem statement:
- $(1, 2, 3)$
- $(1, 3, 4)$
- $(1, 4, 5)$
- $(2, 1, 3)$
- $(3, 1, 4)$
- $(4, 1, 5)$
Sample Input 2
11 1 2 3 4 5 6 123456789123456789 123456789123456789 987654321987654321 987654321987654321 121932631356500531347203169112635269
Sample Output 2
40
Note that the values of each integer $A_i$ can be huge.
Sample Input 3
9 4 4 4 2 2 2 1 1 1
Sample Output 3
162
Note that there may be duplicates among the values of $A_i$.
Input
Output
分数: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$ 的值可能存在重复。