2768 - Very Simple Task

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

2768 - Very Simple Task

Post by ymondelo20 » 6 years ago



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

hanimal
Posts: 9
Joined: 5 years ago
Gender: None specified

Re: 2768 - Very Simple Task

Post by hanimal » 5 years ago

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
Posts: 97
Joined: 6 years ago
Gender: None specified

Re: 2768 - Very Simple Task

Post by humbertodiaz » 5 years ago

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
Posts: 9
Joined: 5 years ago
Gender: None specified

Re: 2768 - Very Simple Task

Post by hanimal » 5 years ago

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
Posts: 97
Joined: 6 years ago
Gender: None specified

Re: 2768 - Very Simple Task

Post by humbertodiaz » 5 years ago

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

hanimal
Posts: 9
Joined: 5 years ago
Gender: None specified

Re: 2768 - Very Simple Task

Post by hanimal » 5 years ago

(pow(2,a+1))))-1)%1000000007
Last edited by hanimal on Mon Mar 02, 2015 5:05 pm, edited 1 time in total.

humbertodiaz
Posts: 97
Joined: 6 years ago
Gender: None specified

Re: 2768 - Very Simple Task

Post by humbertodiaz » 5 years ago

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
Posts: 9
Joined: 5 years ago
Gender: None specified

Re: 2768 - Very Simple Task

Post by hanimal » 5 years ago

Como cual? Hay algun algoritmo o metodo?

humbertodiaz
Posts: 97
Joined: 6 years ago
Gender: None specified

Re: 2768 - Very Simple Task

Post by humbertodiaz » 5 years ago

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
Posts: 9
Joined: 5 years ago
Gender: None specified

Re: 2768 - Very Simple Task

Post by hanimal » 5 years ago

Ok, ya vi eso y me dio, Gracias

Post Reply

Return to “Problem set”