ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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
ｅｓａｓｅｌｐ　ｅｍ　ｌｌｅｔ
Re: This problem has fine precalc solution
Posted by chonglinsun 10 Jul 2009 11:54
Re: This problem has fine precalc solution
Posted by Cat36 13 Jul 2009 11:08
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?