3377 - Fun with Divisors
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.
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.
- ymondelo20
- Posts: 1968
- Joined: 9 years ago
- Location: Universidad de las Ciencias Informáticas
- Gender:
- Contact:
- ymondelo20
- Posts: 1968
- Joined: 9 years ago
- Location: Universidad de las Ciencias Informáticas
- Gender:
- Contact:
Re: 3377 - Fun with Divisors
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.
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. 

Re: 3377 - Fun with Divisors
¿Este problema no es el mismo que el http://coj.uci.cu/24h/problem.xhtml?pid=3245 ?
teruel
- ymondelo20
- Posts: 1968
- Joined: 9 years ago
- Location: Universidad de las Ciencias Informáticas
- Gender:
- Contact:
Re: 3377 - Fun with Divisors
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.
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. 

Re: 3377 - Fun with Divisors
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