bristy's blog

FIBONACCI in log(n)
By bristy, 15 years ago, In English
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?
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
15 years ago, hide # |
← Rev. 2  
Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
In this problem you can do it in O(1), as M is <= 20 and the sequence (Fn mod M) will loop.
→ Reply