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

How can i calculate the the (nth fibonacci)th fibonacci number mod M with (n, M <= 10^9)
Автор hoainiem, история, 2 года назад, По-английски

I have a problem about fibonacci numbers: ==================

let f[i] be the ith fibonacci number

f[i] = 1 (1 <= i <= 2)

f[i] = f[i-1] + f[i-2] (i > 2)

how can i calculate f[f[n]] mod M (n, M <= 10^9). anyone can help me?

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by hoainiem (previous revision, new revision, compare).

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

https://codeforces.com/blog/entry/18292

→ Ответить
  • »
    »
    2 года назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    i don't think these 2 problems are similar. your problem is calculate the nth fibonacci number , which can be solved by matrix multiplication. but we can't use it to solve my problem because f[n] can be very large, and we can't use modules because (f[f[n]]) mod m is not equal to (f[f[n]mod m] ) mod m

    → Ответить
»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I guess you can try to find pisano period of M, then calculate f[n] mod P(m), where P(i) — pisano period of modulo i, and then calculate the final answer mod M.

Though I'm not sure how to calculate pisano period for such big M, you can try to look for some optimizations here.(also google is your big friend here)

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

Here is the solution https://www.youtube.com/watch?v=dQw4w9WgXcQ

→ Ответить