3377 - Fun with Divisors

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:

3377 - Fun with Divisors

Postby ymondelo20 » Thu Oct 01, 2015 4:21 pm



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

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:

Re: 3377 - Fun with Divisors

Postby ymondelo20 » Mon Oct 26, 2015 2:49 pm

Todo número N se descompone como N = p1 ^ (k1) + p2 ^ (k2) + ... + pR ^ (kR) siendo p1,p2,...,pR números primos diferentes y k1,k2,...kR números enteros no negativos. Luego de ello, la cantidad de divisores de N se obtiene mediante la fórmula DIVISORES ( N ) = (k1 + 1) * (k2 + 1) * ... * (kR + 1).
Conocido lo anterior, se puede usar backtracking para encontrar el número que se pide.
Siempre otorgando al menor número primo el mayor exponente.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

HaZard
Posts: 113
Joined: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 3377 - Fun with Divisors

Postby HaZard » Tue Nov 03, 2015 11:45 am

¿Este problema no es el mismo que el http://coj.uci.cu/24h/problem.xhtml?pid=3245 ?
teruel

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:

Re: 3377 - Fun with Divisors

Postby ymondelo20 » Thu Nov 05, 2015 11:44 am

NO...
Se diferencian en "at least N divisors" y "exactly N divisors".
El último es por mucho más fácil de resolver. Voy a adicionar un análisis y verás.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

HaZard
Posts: 113
Joined: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 3377 - Fun with Divisors

Postby HaZard » Mon Nov 07, 2016 6:05 am

es verdad que no es lo mismo, pero este problema también se puede resolver con programación dinámica, incluso si se aumentan los rangos del problema, Saludos
teruel


Return to “Problem set”

Who is online

Users browsing this forum: No registered users and 1 guest