Обсуждение @ 1133. Последовательность Фибоначчи @ Timus Online Judge

This problem has fine precalc solution

Послано Cat36 15 май 2009 18:43

)

Re: This problem has fine precalc solution

Послано chonglinsun 10 июл 2009 11:54

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

Re: This problem has fine precalc solution

Послано chonglinsun 10 июл 2009 11:54

tell me please

Re: This problem has fine precalc solution

Послано Cat36 13 июл 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

Послано ASK 4 ноя 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

Послано Artem Khizha [DNU] 16 янв 2011 16:40

What about its complexity?

Обсуждение задачи 1133. Последовательность Фибоначчи