2768 - Very Simple Task

[ymondelo20]

http://coj.uci.cu/24h/problem.xhtml?abb=2768

[hanimal]

Buenas, Alguien me puede decir porque si la formula que satisface lo que pide el ejercicio, que en forma general seria dada una constante(c)
((c^(i+1)-1)/c-1 )

en este caso
(2^(i+1)-1)

me da Wrong answer??

Hay algo en especial a tener en cuenta?

Gracias de antemano

Saludos.

[humbertodiaz]

Debes considerar varios aspectos. Primero, N podria tener una valor de hasta 1,000,000. Eso es un valor grande. Segundo, el resultado se debe calcular modulo (10^9 + 7). Quizas, asegura que tu solucion esta correcta para N = 40?

[hanimal]

Si, la variable seria long, aunque en un entero entra y al final del calculo modulo, pero no me da, asi es como lo estaba intentando .

Saludos.

[humbertodiaz]

Podrias poner tu codigo aqui por un momento? Asi te podria decir si veo algo mal.

[hanimal]

(pow(2,a+1))))-1)%1000000007

[humbertodiaz]

Eso no funcionaria. Intentas calcular 2^(N+1) primero, pero no puedes calcular ese valor directamente con pow(). El resultado podria ser mucho mas de lo que puedes guardar dentro de cualquier tipo normal. Necesitas usar otro metodo que te permita aplicar modulo para los resultados intermedios.

[hanimal]

Como cual? Hay algun algoritmo o metodo?

[humbertodiaz]

Hay un algoritmo para hacer exponenciacion eficientemente. Se conoce como exponenciacion binaria:

http://es.wikipedia.org/wiki/Exponencia ... 3n_binaria

Puedes modificar ese metodo para tomar modulo despues de cada multiplicacion, y asi aseguras que nunca tengas un resultado demasiado grande. Asumiendo que usas long long para tus calculos. Ese articulo da un ejemplo de aplicar modulo en el proceso. El proceso de elevar un numero a una potencia mientras se aplica modulo se llama "exponenciacion modular".

[hanimal]

Ok, ya vi eso y me dio, Gracias