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.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3377 - Fun with Divisors

Post by ymondelo20 » 3 years ago



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

User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3377 - Fun with Divisors

Post by ymondelo20 » 3 years ago

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: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 3377 - Fun with Divisors

Post by HaZard » 3 years ago

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

User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3377 - Fun with Divisors

Post by ymondelo20 » 3 years ago

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: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 3377 - Fun with Divisors

Post by HaZard » 1 year ago

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

Post Reply

Return to “Problem set”