bristy's blog

FIBONACCI in log(n)
By bristy, 13 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

»
13 years ago, # |
← 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
»
13 years ago, # |
  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
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    M ≤ 220
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Ah, didn't notice that we are looking Fn modulo 2^M.

      Anyway, the O(1) is still true, but the constant would be quite big ;)
      → Reply