Solución a “Números Libres”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 1
Autor: Freddy Román Cepeda
Fuente: Edgar Augusto Santiago Nieves

Para resolver este problema hacía falta tener en mente la definición de square-free. Como tanto a y b no son divisibles por el cuadrado de un primo, la única manera de que su producto deje de ser square-free sería que ambos compartieran un factor primo.

Para obtener todos los puntos de la primer subtarea bastaba con computar a \times b e iterar sobre todos los números menores a ese producto y revisar si es divisible por el cuadrado de alguno de ellos.

Para obtener los puntos de la segunda subtarea era suficiente iterar hasta \max(\sqrt{a}, \sqrt{b}), para factorizar a a y b.

Por último, para obtener el resto de los puntos bastaba notar que si a y b comparten un factor primo, entonces su máximo común divisor es distinto de 1.

El siguiente código implementa esta solución:

One thought on “Solución a “Números Libres”

  1. Hey muchas gracias por esta ayuda. Ya me estaba desesperando por poder encontra la solución a este problema.
    Saludos!

Leave a Reply