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: