We are given an array A. We have to find the number of pairs with following conditions

1. i<j
2. A[i]=A[j]
3. i*j is divisible by X

Have to do this in something better than O(N * N). I used an approach with hashmap to store all indices with condition 2 in one array, and that element as key, but that solution was not efficient enough. I think it has something to do with GCD. Any help is appreciated.

Sample input:
A: [ 2,3,4,3,3,2,3,3]
X: 2

Sample output:
10

eg:
(1,6)
(2,4)
(2,5)
(2,7)
(2,8)
(4,5)
(4,7)
(4,8)
(5,8)
(7,8)