La idea es calcular la respuesta por partes, primero se cuentan los pares ~(i, j, k)~ tal que ~(i < j < k)~ y su producto sea a lo más n, luego los pares ~(i, i, j)~ tal que ~i \neq j~ y finalmente los pares ~(i, i, i)~. La respuesta final será ~cnt_{(i,j,k)} \cdot 6 + cnt_{(i,i,j)} \cdot 3 + cnt_{(i, i, i)}~ (note que son las formas de permutar los números de las tuplas).

Para calcular los de primer tipo, se puede notar que ~i \leq n^{\frac{1}{3}}~, ya que la multiplicación de 3 números mayores que ~n^{\frac{1}{3}}~ es mayor que ~n~. Similarmente ~j \leq \sqrt{n}~, así que podemos probar todos los pares de ~i~ y ~j~ y ver cuales ~k~ le son válidos es simplemente ~\min( \frac{n}{i \cdot j} - j , 0 )~.

Para calcular los del segundo tipo podemos probar todos los pares de ~(i, j)~ ya que ~i \leq \sqrt(n)~ por lo explicado anteriormente.

Para calcular los del tercer tipo probamos todos los ~i~.

Complejidad ~O(n \cdot \sqrt{n})~ o ~O(n)~ dependiendo de la implementación.