Page 1 of 1

3560 - How Many Square Free Numbers

Posted: Fri Apr 08, 2016 1:39 am
by ymondelo20

Re: 3560 - How Many Square Free Numbers

Posted: Mon Oct 24, 2016 4:39 pm
by frankr
Solución. Es necesario probar lo siguiente:

* El producto A*B de dos números square free A y B es square free sí y solo sí A y B son primos relativos.
* El producto de N números square free es square free también sí y solo sí ellos son primos relativos dos a dos.

Una vez que se demuestre lo anterior el problema se reduce a examinar solo los 2^N - 1 subconjuntos no vacíos y cada vez que tengamos un subconjunto donde todos sus elementos son primos dos a dos entonces contarlo sí su producto no ha aparecido antes, para saber esto se puede usar alguna función hash. Sí se desea evitar posibles colisiones de los valores hash entonces es necesario emplear algún algoritmo de factorización efeciente para los rangos propuestos.

Re: 3560 - How Many Square Free Numbers

Posted: Mon Oct 24, 2016 4:45 pm
by frankr
Este problema es una versión más fuerte o generalizada de http://coj.uci.cu/24h/problem.xhtml?pid=2916.