De ce contează?
Gândește-te la zilele săptămânii. Sunt doar șapte: luni, marți, ..., duminică, apoi iarăși luni. Dacă azi e marți și cineva te întreabă ce zi va fi peste 1000 de zile, nu numeri o mie de zile pe degete. Știi că totul se repetă din 7 în 7, așa că te uiți doar la ce rămâne după ce scoți săptămânile întregi. Aceeași idee simplă rezolvă probleme în care indicele cerut e atât de mare încât nici nu poate fi parcurs.
Ideea-cheie
Această punte nu aduce un algoritm nou. Aduce o singură observație care îți schimbă reflexul când vezi un indice uriaș.
Imaginează-ți un șir în care fiecare termen se calculează din cel dinainte
folosind o operație cu rest (un modulo). Restul la m nu poate lua decât m
valori posibile: 0, 1, 2, ..., m-1. Sunt finite. Dacă șirul merge mai departe
de m pași, prin forța lucrurilor o valoare deja apărută trebuie să revină —
n-are unde altundeva să se ducă. Iar din clipa în care o stare se repetă, tot ce
urmează se repetă identic: șirul intră într-un ciclu de o anumită lungime,
numită perioadă.
Stările posibile sunt mărginite (doar m resturi), dar pașii sunt nelimitați.
O mulțime finită parcursă la infinit se repetă obligatoriu. De aici declicul: în
loc să parcurgi miliarde de pași, găsești perioada P și apoi termenul cu
indicele N „arată" la fel ca termenul cu indicele N mod P.