El problema pide hallar para cada número ~x~ de la entrada cuantos números ~y~ hay tal que ~y~ divide a ~x~. Para esto podemos hallar la frecuencia de cada número en el arreglo y hacer algo parecido a una Criba de Eratóstenes:

for(int i = 1; i < MAX; i++)
    for(int j = i; j < MAX; j += i)
        sol[j] += freq[i]; //freq[i] es la frecuencia del número i

Lo que quedaría sería imprimir ~sol[a[i]] - 1~ para cada ~i \; (1 \leq i \leq n)~.

Complejidad: ~O(MAX \log MAX)~. Esto es porque se puede demostrar que para un natural ~n~ se cumple que ~n + n / 2 + n / 3 + \ldots + 1 = O(n \log n)~.