A*B*C.
Submit solution
Points:
100 (partial)
Time limit:
2.0s
Memory limit:
1G
Authors:
Problem type
Allowed languages
Ada, Brain****, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB
Dado un entero positivo , calcule el número de triples de enteros positivos
tales que
. Dos triples con los mismos números en diferente orden son considerados diferentes.
Entrada
La entrada contendra un entero .
Salida
Imprime el número de triples de enteros positivos tal que
.
Restricciones
.
es un entero.
Ejemplo #1 de Entrada
2
Ejemplo #1 de Salida
4
Tenemos los siguientes triples: ,
,
,
.
Ejemplo #2 de Entrada
10
Ejemplo #2 de Salida
53
Ejemplo #3 de Entrada
31415
Ejemplo #3 de Salida
1937281
Comments
Increíblemente esto se puede hacer usando 3 bucles for anidados, solo que en cada condición debes de poner la multiplicación del iterador actual por los anteriores que sea menor o igual a N:
Al menos yo lo hice así y en el peor caso de prueba me dio 0.025 de tiempo.
Hola amigo , interesante solucion y felicidades x el AC pero para el progreso de las personas este tipo de comentarios deberian ir en las editoriales :)
el AC que mas he esperado en toda mi vida
Voy a compartir mi solución, que es un tanto diferente a la de la editorial.
Primero computemos
: cantidad de pares
tales que
.
Una vez que tenemos
, cómo lo usamos para calcular los tríos
tales que
.
Si
está fijo, entonces
.
Por tanto, iteramos por
, y a la respuesta la añadimos
. Eso toma tiempo lineal.
Ahora, cómo computar
para todo
.
Si
, entonces
es divisor de
, y para cada
distinto,
es único. Eso quiere decir que la cantidad de pares que su producto es exactamente
, es igual a la cantidad de divisores de
.
Entonces
. 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
, y para cada
, iterar por sus múltiplos
, y añadirle 1 a la cantidad de divisores de
.
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
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).
La solución que no debería ser es la O(n^3), no veo la otra forma
tambien se puede hacer en O(n^2) y entra en tiempo.
Iteramos con tres variables
. 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.