Programa que dado una lista de longitud n encuentra todas las ternas i, j y k con i <= j tal que a[i] * a[j] = a[k]

Estoy tratando de averiguar cómo puedo escribir un programa de manera que una lista de longitud n encuentre todas las tripletas i, j y k con i <= j tal que a[i] * a[j] = a[k] y devuelva la cantidad de veces que esto ocurre. La solución obvia es un triple bucle que tiene un tiempo de ejecución de O(n^3) de la siguiente manera.

public static int count(int[] a) {
    int total = 0;
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a.length; j++) {
            if (a[i] <= a[j]) {
                for (int k = 0; k < a.length; k++) {
                    if (a[i] * a[j] == a[k])
                        total++;
                }
            }
        }
    }
    return total;
}

Pero se me ocurrió una forma más rápida utilizando hashsets de esta manera.

public static int count(int[] a) { // O(n^2)
    int total = 0;
    Set<integer> set = new HashSet<>();
    for (int i : a) { // O(n)
        set.add(i); // O(1)
    }
    for (int i : a) { // O(n^2)
        for (int j : a) {
            if (i <= j) {
                if (set.contains(i * j)) // O(1)
                    total++;
            }
        }
    }
    return total;
}

Esta tiene un tiempo de ejecución de O(n^2). ¿Es posible hacerlo más rápido que esto?