A*B*C


Submit solution


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

Authors:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

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

Restricciones

  • 1 \leq K \leq 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 \le K.

Ejemplo #1 de Entrada

2

Ejemplo #1 de Salida

4

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

Ejemplo #2 de Entrada

10

Ejemplo #2 de Salida

53

Ejemplo #3 de Entrada

31415

Ejemplo #3 de Salida

1937281

Comments


  • 12
    aniervs  commented on April 7, 2021, 5: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).


  • 2
    angelmh  commented on April 7, 2021, 3:25 p.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


    • 1
      Sekai02  commented on April 7, 2021, 3:38 p.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).


      • 1
        angelmh  commented on April 7, 2021, 4:06 p.m.

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


        • 1
          Yosbany_ossoby  commented on July 13, 2022, 12:13 p.m.

          tambien se puede hacer en O(n^2) y entra en tiempo.


        • 3
          Sekai02  commented on April 7, 2021, 4:59 p.m. edited

          Iteramos con tres variables x, y, z. Sabemos que \(x·y·z \le k\) entonces se tiene siempre que cumplir: \(x\ley\lek/x\) y \(y\lez\lek/(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.