Por Freddy
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 $latex a$ y $latex 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 $latex 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 $latex \max(\sqrt{a}, \sqrt{b})$, para factorizar a $latex a$ y $latex b$.
Por último, para obtener el resto de los puntos bastaba notar que si $latex a$ y $latex b$ comparten un factor primo, entonces su máximo común divisor es distinto de 1.
El siguiente código implementa esta solución: