102493: [AtCoder]ABC249 D - Index Trio
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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
Input
题意翻译
给定序列 $ a_n $,求满足 $ \dfrac{a_i}{a_j} = a_k, 1 \le i, j, k, \le n $ 的不同三元组 $ (i, j, k) $ 的个数。Output
分数: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