Page 1 of 1

3377 - Fun with Divisors

Posted: Thu Oct 01, 2015 4:21 pm
by ymondelo20

Re: 3377 - Fun with Divisors

Posted: Mon Oct 26, 2015 2:49 pm
by 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.

Re: 3377 - Fun with Divisors

Posted: Tue Nov 03, 2015 11:45 am
by HaZard
¿Este problema no es el mismo que el http://coj.uci.cu/24h/problem.xhtml?pid=3245 ?

Re: 3377 - Fun with Divisors

Posted: Thu Nov 05, 2015 11:44 am
by 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.

Re: 3377 - Fun with Divisors

Posted: Mon Nov 07, 2016 6:05 am
by 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