3377 - Fun with Divisors

[ymondelo20]

http://coj.uci.cu/24h/problem.xhtml?pid=3377

[ymondelo20]

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.

[HaZard]

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

[ymondelo20]

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.

[HaZard]

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