3560 - How Many Square Free Numbers

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3560 - How Many Square Free Numbers

Post by ymondelo20 » 2 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
frankr
Posts: 51
Joined: 7 years ago
Location: Las Tunas
Gender: Male

Re: 3560 - How Many Square Free Numbers

Post by frankr » 2 years ago

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.

User avatar
frankr
Posts: 51
Joined: 7 years ago
Location: Las Tunas
Gender: Male

Re: 3560 - How Many Square Free Numbers

Post by frankr » 2 years ago

Este problema es una versión más fuerte o generalizada de http://coj.uci.cu/24h/problem.xhtml?pid=2916.

Post Reply

Return to “Problem set”