Блог пользователя bristy

FIBONACCI in log(n)
Автор bristy, 13 лет назад, По-английски
I try to solve problem on uva id:10229
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1170
its givig me tle.....
i have to find fibonacci number upon mod M.
Can any tell how to do this in log(n) time?
  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

http://www.cplusplus.com/forum/general/16769/
http://e-maxx.ru/algo/fibonacci_numbers#8

→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In this problem you can do it in O(1), as M is <= 20 and the sequence (Fn mod M) will loop.
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I got Accepted
f(i)=(f(i-2)+f(i-1))mod(2^m)
if( f(i)==0 and f(i-1)==1) then ans=f(n%i);
→ Ответить