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.

Comments


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

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


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

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