Rekenen modulo een priemgetal

Antwoorden in wedstrijden kunnen enorm groot worden, veel groter dan welk geheel-getaltype dan ook. Daarom vragen problemen om het resultaat modulo een groot priemgetal, zodat de getallen klein blijven. 🔢

Het priemgetal dat je het vaakst zult zien is 1000000007, vaak geschreven als 1e9+7. Het is net groot genoeg om botsingen te vermijden en klein genoeg om in 64 bits te passen.

De modulo-operator geeft de rest na een deling. Dus 17 % 5 is 2, omdat er bij het delen van 17 door 5 een rest van 2 overblijft.

Je kunt eerst optellen en aan het einde modulo nemen, of tijdens het optellen steeds modulo nemen. De rest is in beide gevallen hetzelfde, dus verklein de waarden regelmatig zodat ze klein blijven.

Dezelfde regel geldt voor vermenigvuldigen: neem het product modulo het priemgetal. Python verwerkt grote gehele getallen standaard, maar modulo nemen houdt elke waarde klein en snel.

Pas in een lange lus bij elke iteratie % MOD toe. Zo voorkom je dat getallen enorm groeien en blijven alle bewerkingen goedkoop en voorspelbaar.

Aftrekken kan in veel talen een negatieve rest opleveren. Tel MOD er vóór de laatste modulo bij op, zodat het resultaat in het veilige bereik vanaf 0 valt.

Goed nieuws: Python geeft met % al een niet-negatief resultaat bij een positieve modulus. Dus -1 % 7 geeft 6 en geen -1, waardoor je geen extra correctie nodig hebt.

Het kernidee: (a op b) % m is voor optellen en vermenigvuldigen gelijk aan (a%m op b%m) % m. Daardoor kun je invoerwaarden verkleinen voordat je ze combineert.

Optellen, aftrekken en vermenigvuldigen werken netjes onder een modulo. Gewone deling doet dat niet, en later in deze cursus heb je daarvoor een modulaire inverse nodig.

Definieer MOD aan het begin van je oplossing als een constante. Eén benoemde waarde is beter dan 1000000007 op allerlei plekken in de code, waar een typefout onopgemerkt kan blijven.

Je houdt enorme aantallen nu klein met een priemmodulus zoals 1e9+7. Verklein optellingen, aftrekkingen en vermenigvuldigingen bij elke stap, let op negatieve waarden en bewaar delingen voor inverses. 🎯