Editorial for A*B*C


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: humbertoyusta

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.


Comments

There are no comments at the moment.