D - Index Trio
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
長さ N の整数列 A = (A_1, \dots, A_N) が与えられます。
以下の条件を全て満たす整数の組 (i, j, k) の総数を求めてください。
- 1 \leq i, j, k \leq N
- \frac{A_i}{A_j} = A_k
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 6 2 3
出力例 1
2
(i, j, k) = (1, 2, 3), (1, 3, 2) が条件を満たします。
入力例 2
1 2
出力例 2
0
入力例 3
10 1 3 2 4 6 8 2 2 3 7
出力例 3
62
Score : 400 points
Problem Statement
You are given an integer sequence A = (A_1, \dots, A_N) of length N.
Find the number of triplets of integers (i, j, k) satisfying all of the conditions below.
- 1 \leq i, j, k \leq N
- \frac{A_i}{A_j} = A_k
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 2 \times 10^5 \, (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print the answer.
Sample Input 1
3 6 2 3
Sample Output 1
2
(i, j, k) = (1, 2, 3), (1, 3, 2) satisfy the conditions.
Sample Input 2
1 2
Sample Output 2
0
Sample Input 3
10 1 3 2 4 6 8 2 2 3 7
Sample Output 3
62