Pisano Period of Large Numbers

Правка en4, от neverblunder, 2020-10-10 20:25:06

Hi, hope you all have a good day (or a good night, it's midnight in my area lol). Recently I came across a problem, which takes two integers — n and m — as input, with 3 <= n, m <= 10^9. The problem asks for the value of F(F(i)) mod m, with F(i) denoting the i-th Fibonacci number. I'm not sure if this question has been asked before on any platform (though I'm pretty sure no one has asked about it on English Competitive Programming Forums), but this seems to be a direct application of the Pisano Period. However, I am only able to find an O(m^2) algorithm, which does not suffice the condition of this problem. Even though there seems to be a fast enough algorithm on mathoverflow, the writer said that this algorithm may fail with specific prime numbers. So, my question is does there exist a precise method of calculating the pisano period of large number >= 10^9 ? Thanks in advance for your responses, I will really appreciate your helps.

Теги #math, fibonacci, pisano

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский neverblunder 2020-10-10 21:28:16 4 Tiny change: 'r helps.\n**Update' -> 'r helps.\n\n\n**Update'
en6 Английский neverblunder 2020-10-10 21:27:38 195
en5 Английский neverblunder 2020-10-10 20:25:50 15 Small grammatical changes
en4 Английский neverblunder 2020-10-10 20:25:06 5 Tiny change: 'eger), there said that' -> 'eger), the writer said that'
en3 Английский neverblunder 2020-10-10 20:17:14 2 Tiny change: 'd an `O(m^{2})` algorit' -> 'd an `O(m^2)` algorit'
en2 Английский neverblunder 2020-10-10 20:13:32 44 Tiny change: 'Hi, hope y' -> '``Hi, hope y' (published)
en1 Английский neverblunder 2020-10-10 20:10:00 1096 Initial revision (saved to drafts)