Finding number of pairs, product of whose indices is divisible by another number X

First of all, store separate search structures for each distinct A[i] as we iterate.

i * j = k * X
i = k * X / j

Let X / j be some fraction. Since i is an integer, k would be of the form m * least_common_multiple(X, j) / X, where m is natural.

Example 1: j = 20, X = 60:

lcm(60, 20) = 60
matching `i`s would be of the form:
(m * 60 / 60) * 60 / 20
=> m * q, where q = 3

Example 2: j = 6, X = 2:

lcm(2, 6) = 6
matching `i`s would be of the form:
(m * 6 / 2) * 2 / 6
=> m * q, where q = 1

Next, I would consider how to efficiently query the number of multiples of a number in a sorted list of arbitrary naturals. One way is to hash the frequency of divisors of each i we add to the search structure of A[i]. But first consider i as j and add to the result the count of divisors q that already exist in the hash map.

JavaScript code with brute force testing at the end:

function gcd(a, b){
  return b ? gcd(b, a % b) : a;
}


function getQ(X, j){
  return X / gcd(X, j);
}


function addDivisors(n, map){
  let m = 1;
    
  while (m*m <= n){
    if (n % m == 0){
      map[m] = -~map[m];
      
      const l = n / m;
      
      if (l != m)
        map[l] = -~map[l];
    }
    
    m += 1;
  }
}


function f(A, X){
  const Ais = {};
  let result = 0;
  
  for (let j=1; j<A.length; j++){
    if (A[j] == A[0])
      result += 1;

    // Search
    if (Ais.hasOwnProperty(A[j])){
      const q = getQ(X, j);

      result += Ais[A[j]][q] || 0;
    
    // Initialise this value's
    // search structure
    } else {
      Ais[A[j]] = {};
    }
    
    // Add divisors for j
    addDivisors(j, Ais[A[j]]);
  }
  
  return result;
}


function bruteForce(A, X){
  let result = 0;
  
  for (let j=1; j<A.length; j++){
    for (let i=0; i<j; i++){
      if (A[i] == A[j] && (i*j % X) == 0)
        result += 1;
    }
  }
  
  return result;
}


var numTests = 1000;
var n = 100;
var m = 50;
var x = 100;

for (let i=0; i<numTests; i++){
  const A = [];

  for (let j=0; j<n; j++)
    A.push(Math.ceil(Math.random() * m));
    
  const X = Math.ceil(Math.random() * x);
  
  const _brute = bruteForce(A, X);
  const _f = f(A, X);

  if (_brute != _f){
    console.log("Mismatch!");
    console.log(X, JSON.stringify(A));
    console.log(_brute, _f);
    break;
  }
}

console.log("Done testing.")

Just in case If someone needed the java version of this answer - https://stackoverflow.com/a/69690416/19325755 explanation has been provided in that answer.

I spent lot of time in understanding the javascript code so I thought the people who are comfortable with java can refer this for better understanding.

import java.util.HashMap;

public class ThisProblem {

public static void main(String[] args) {
    int t = 1000;
    int n = 100;
    int m = 50;
    int x = 100;
    for(int i = 0; i<t; i++) {
        int[] A = new int[n];
        for(int j = 0; j<n; j++) {
            A[j] = ((int)Math.random()*m)+1;
        }
        int X = ((int)Math.random()*x)+1;
        int optR = createMaps(A, X);
        int brute = bruteForce(A, X);
        if(optR != brute) {
            System.out.println("Wrong Answer");
            break;
        }
    }
    System.out.println("Test Completed");
}

public static int bruteForce(int[] A, int X) {
    int result = 0;
    int n = A.length;
    for(int i = 1; i<n; i++) {
        for(int j = 0; j<i; j++) {
            if(A[i] == A[j] && (i*j)%X == 0)
                result++;
        }
    }
    return result;
}

public static int gcd(int a, int b) {
    return b==0 ? a : gcd(b, a%b);
}

public static int getQ(int X, int j) {
    return X/gcd(X, j);
}

public static void addDivisors(int n, HashMap<Integer, Integer> map) {
    int m = 1;
    while(m*m <= n) {
        if(n%m == 0) {
            map.put(m, map.getOrDefault(m, 0)+1);
            int l = n/m;
            if(l != m) {
                map.put(l, map.getOrDefault(l, 0)+1);
            }
        }
        m++;
    }
}

public static int createMaps(int[] A, int X) {
    int result = 0;
    HashMap<Integer, HashMap<Integer, Integer>> contentsOfA = new HashMap<>();
    int n = A.length;
    for(int i = 1; i<n; i++) {
        if(A[i] == A[0])
            result++;
        if(contentsOfA.containsKey(A[i])) {
            int q = getQ(X, i);
            result += contentsOfA.get(A[i]).getOrDefault(q, 0);
        } else {
            contentsOfA.put(A[i], new HashMap<>());
        }
        addDivisors(i, contentsOfA.get(A[i]));
    }
    return result;
}

}