ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1133. Fibonacci Sequence

This problem has fine precalc solution
Posted by Cat36 15 May 2009 18:43
)
Re: This problem has fine precalc solution
Posted by chonglinsun 10 Jul 2009 11:54
esaselp em llet
Re: This problem has fine precalc solution
Posted by chonglinsun 10 Jul 2009 11:54
tell me please
Re: This problem has fine precalc solution
Posted by Cat36 13 Jul 2009 11:08
sorry, bad english
This sequence can be calculated as k1*((1+sqrt(5))/2)^n +k2*((1-sqrt(5))/2)^n
By precalculation we can find such prime p, what:
 1. p>4000000000;
 2. exist such n, what n*n==5 (mod p)
So, this sequence by modulo p can be calculated us k1*a^n + k2*b^n, where a,b,k1,k2 - integer

It's all

Edited by author 13.07.2009 11:09
sqrt(5) = 2162366358 mod 4000000019
Posted by ASK 4 Nov 2010 23:35
Note that if you go this road, you are better using Java, since you will need modPow and modInverse.
Re: This problem has fine precalc solution
Posted by Artem Khizha [DNU] 16 Jan 2011 16:40
What about its complexity?