aditya_sheth's blog

By aditya_sheth, history, 2 months ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it