This problem has fine precalc solution

Posted by

Cat36 15 May 2009 18:43

)

Re: This problem has fine precalc solution

ｅｓａｓｅｌｐ ｅｍ ｌｌｅｔ

Re: This problem has fine precalc solution

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

What about its complexity?