Editorial for Another Contest 8 Problem 3 - Replay Double Ignition

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The Fibonacci sequence modulo M repeats in \mathcal{O}(M) elements. Therefore, we can compute the whole string before a repeat and then answer queries by taking indices modulo the length of that string.


  • -4
    youcefs21  commented on Aug. 30, 2021, 6:30 p.m.

    it does repeat eventually, but not always in O(M) elements, for example when M = 10, it repeats in 60 elements

    • 8
      DM__Oscar  commented on Aug. 30, 2021, 6:35 p.m.

      Big O doesn't care about constants, only asympototical behaviour.