How to solve this Fibonacci sequence problem?

Revision en3, by aditya_sheth, 2020-04-02 14:20:29

A sequence of integer numbers a0, a1, . . . , an, . . . , is called the Fibonacci sequence modulo r if a0 = 0, a1 = 1, and ai = (ai−2 + ai−1) mod r for all i ≥ 2. A number p > 0 is called the period of the sequence, if there is some i0, such that for all i ≥ i0 the equation ai = ai+p is satisfied. The sequence is called periodic if it has a period. Clearly, if the sequence is periodic, it has the smallest period. Given r you have to find whether the sequence Fr is periodic, and if it is what is its smallest period. Constraints: 2 <= r <= 2*10^9

Link to the problem: Problem E.

Tags asc, fibonacci sequence

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English aditya_sheth 2020-04-02 14:20:29 32 Tiny change: ' period.\n\nLink t' -> ' period.\nConstraints:\n2 <= r <= 2*10^9\n\nLink t'
en2 English aditya_sheth 2020-04-02 14:17:19 0 (published)
en1 English aditya_sheth 2020-04-02 14:15:14 654 Initial revision (saved to drafts)