A*B*C - DMOJ: Modern Online Judge

ABC

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 1G

Authors:

Leonardo, FrankHG, humbertoyusta

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

Dado un entero positivo $K$ ~K~, calcule el número de triples de enteros positivos $(A, B, C)$ ~(A, B, C)~ tales que $A*B*C \le K$ ~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$ ~1 \leq K \leq 2.10^5~.
$K$ ~K~ es un entero.

Entrada

La entrada contendra un entero $K$ ~K~.

Salida

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

Ejemplo #1 de Entrada

Ejemplo #1 de Salida

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

Ejemplo #2 de Entrada

Ejemplo #2 de Salida

Ejemplo #3 de Entrada

Ejemplo #3 de Salida

Comments

11

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)$ ~s(n)~: cantidad de pares $a, b$ ~a, b~ tales que $a\cdot b \le n$ ~a\cdot b \le n~.

Una vez que tenemos $s(n)$ ~s(n)~, cómo lo usamos para calcular los tríos $a, b, c$ ~a, b, c~ tales que $a\cdot b \cdot c \le K$ ~a\cdot b \cdot c \le K~. Si $a$ ~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$ ~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)$ ~s(n)~ para todo $n \le K$ ~n \le K~.

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

Si $x\cdot y = n$ ~x\cdot y = n~, entonces $x$ ~x~ es divisor de $n$ ~n~, y para cada $x$ ~x~ distinto, $y$ ~y~ es único. Eso quiere decir que la cantidad de pares que su producto es exactamente $n$ ~n~, es igual a la cantidad de divisores de $n$ ~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$ ~i \le K~, y para cada $i$ ~i~, iterar por sus múltiplos $j: j \le K$ ~j: j \le K~, y añadirle 1 a la cantidad de divisores de $j$ ~j~.

$i$ ~i~ tiene $\left\lfloor\dfrac{K}{i}\right\rfloor$ ~\left\lfloor\dfrac{K}{i}\right\rfloor~ múltiplos menores o iguales que $K$ ~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)$ .

1

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.

2

Sekai02 commented on April 7, 2021, 4:59 p.m. ← edited →

Iteramos con tres variables $x, y, z$ ~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.