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.
User avatar
ymondelo20
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3560 - How Many Square Free Numbers

Postby ymondelo20 » Fri Apr 08, 2016 1:39 am



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

User avatar
frankr
Posts: 49
Joined: Fri Nov 18, 2011 8:09 pm
Location: Las Tunas
Gender: Male

Re: 3560 - How Many Square Free Numbers

Postby frankr » Mon Oct 24, 2016 4:39 pm

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: 49
Joined: Fri Nov 18, 2011 8:09 pm
Location: Las Tunas
Gender: Male

Re: 3560 - How Many Square Free Numbers

Postby frankr » Mon Oct 24, 2016 4:45 pm

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


Return to “Problem set”

Who is online

Users browsing this forum: No registered users and 1 guest