Discussion @ 1133. Fibonacci Sequence @ Timus Online Judge

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

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?

Discussion of Problem 1133. Fibonacci Sequence