Submit solution


Points: 100 (partial)
Time limit: 2.0s
Memory limit: 1G

Authors:
Problem type
Allowed languages
C, C++, Java, Pascal, Python

Dado un entero positivo \(K\), calcule el número de triples de enteros positivos \((A, B, C)\) tales que \(A*B*C≤K\).Dos triples con los mismos números en diferente orden son considerados diferentes.

Restricciones

  • \(1≤K≤2×10^5\).
  • \(K\) es un entero.

Entrada:

La entrada contendra un entero \(K\).

Salida:

Imprime el número de triples de enteros positivos \((A, B, C)\) tal que \(A*B*C≤K\).

Entrada de ejemplo 1:

2

Salida de ejemplo 1:

4

Tenemos los siguientes triples: \((1,1,1)\), \((1,1,2)\), \((1,2,1)\), \((2,1,1)\).

Entrada de ejemplo 2:

10

Salida de ejemplo 2:

53

Entrada de ejemplo 3:

31415

Salida de ejemplo 3:

1937281

Comments


  • 2
    aniervs  commented on April 7, 2021, 1:02 p.m. edited

    Voy a compartir mi solución, que es un tanto diferente a la de la editorial.

    Primero computemos \(s(n)\): cantidad de pares \(a, b\) tales que \(a\cdot b \le n\).

    Una vez que tenemos \(s(n)\), cómo lo usamos para calcular los tríos \(a, b, c\) tales que \(a\cdot b \cdot c \le K\). Si \(a\) está fijo, entonces \(b\cdot c \le \frac{K}{a} \iff b\cdot c \le \left\lfloor\frac{K}{a}\right\rfloor\).

    Por tanto, iteramos por \(a\), y a la respuesta la añadimos \(s\left(\left\lfloor\frac{K}{a}\right\rfloor\right)\). Eso toma tiempo lineal.

    Ahora, cómo computar \(s(n)\) para todo \(n \le K\).

    \(s(n) = s(n-1) + \text{cantidad de pares que su producto es exactamente } n\).

    Si \(x\cdot y = n\), entonces \(x\) es divisor de \(n\), y para cada \(x\) distinto, \(y\) es único. Eso quiere decir que la cantidad de pares que su producto es exactamente \(n\), es igual a la cantidad de divisores de \(n\). Entonces \(s(n) = s(n - 1) + \text{cantidad de divisores de } n\). Eso también toma tiempo lineal una vez que tenemos la cantidad de divisores de cada número.

    Para hallar la cantidad de divisores de cada número, podemos iterar por cada número \(i \le K\), y para cada \(i\), iterar por sus múltiplos \(j: j \le K\), y añadirle 1 a la cantidad de divisores de \(j\).

    \(i\) tiene \(\left\lfloor\dfrac{K}{i}\right\rfloor\) múltiplos menores o iguales que \(K\), así que la complejidad temporal es \(\mathcal{O}\left(\sum_{i = 1}^K \left\lfloor\frac{K}{i}\right\rfloor\right) = \mathcal{O}(K\cdot \log K)\).


  • 0
    angelmh  commented on April 7, 2021, 11:25 a.m.

    Este problema está interesante, mi solución final no estaba muy alejada de la realidad, he corregido ya las deficiencias que he encontrado, todo da bien pero da TLE, ¿cómo bajar el tiempo de este problema? cuento con 3 partes para calcular. O sea, calculo cant(i,j,k), calculo cant(i,i,j) y cant(i,i,i). Creo que la parte lenta está en cant(i,j,k) donde i <= raizCubica(n), j <= raizCuadrada(n) y k <= n/2


    • 0
      Sekai02  commented on April 7, 2021, 11:38 a.m.

      Prueba resolverlo de manera genérica, es decir elimina esos casos aparte que creaste (créeme te complicaste porgusto), luego trata de resolver el problema dividiendo en vez de multiplicando (a veces resolver el problema de atrás hacia delante resulta beneficioso).


      • 0
        angelmh  commented on April 7, 2021, 12:06 p.m.

        La solución que no debería ser es la O(n^3), no veo la otra forma


        • 0
          Sekai02  commented on April 7, 2021, 12:59 p.m. edited

          Iteramos con tres variables \(x, y, z\). Sabemos que \(x·y·z ≤ k\) entonces se tiene siempre que cumplir: \(x≤y≤k/x\) y \(y≤z≤k/(x·y)\), por lo que nunca harás mas de \(O(n⋅√n)\) operaciones. Ya solo te queda ver cuanto te aporta cada tupla. Espero que te sea suficiente este hint para resolver el problema.