Pair Condition :
Difficulty Level : Hard
Submissions : 158
Asked In :
Marks :10
: 2 | : 3
We are given an array $$$A$$$ and an integer $$$X$$$. We have to find the number of pairs with the following conditions:
1. $$$i<j$$$
2. $$$A[i]=A[j]$$$
3. $$$i*j$$$ is divisible by $$$X$$$
We use 1-based indexing in this problem.
Input
The first line contains two integers, $$$n$$$ $$$(1 \le n \le 10^5)$$$ and $$$x$$$ $$$(1 \le x \le 10^9)$$$.
The second line contains $$$n$$$ integers, $$$A_1,A_2,...A_n$$$, $$$(1 \le A_i \le 10^9)$$$.
Output
Return the total number of pairs satisfying the given condition.
Example
Input
3 2 2 2 2
Output
2
