Regn modulo et primtall

Svar i konkurranser kan bli enorme, langt større enn alle heltallstyper andre steder. Derfor ber oppgaver deg finne resultatet modulo et stort primtall, slik at tallene holder seg små. 🔢

Primtallet du oftest vil møte, er 1000000007, ofte skrevet 1e9+7. Det er akkurat stort nok til å unngå kollisjoner og lite nok til å få plass i 64 biter.

Modulo-operatoren gir resten etter en divisjon. Derfor er 17 % 5 lik 2, fordi 17 gir resten 2 når tallet deles på 5.

Du kan addere først og ta modulo til slutt, eller bruke modulo underveis. Resten blir den samme uansett, så reduser ofte for å holde tallene små.

Den samme regelen gjelder for multiplikasjon: ta produktet modulo primtallet. Python håndterer store heltall innebygd, men modulo holder hver verdi liten og operasjonene raske.

I en lang løkke bruker du % MOD i hver iterasjon. Det hindrer tallene i å vokse ukontrollert og holder hver operasjon billig og forutsigbar.

Subtraksjon kan gi en negativ rest i mange språk. Legg til MOD igjen før den siste modulo-operasjonen, slik at resultatet havner i det gyldige området fra 0.

Gode nyheter: Pythons % gir allerede et ikke-negativt resultat når moduloen er positiv. Derfor blir -1 % 7 lik 6, ikke -1, og du slipper en ekstra korrigering.

Hovedideen er at (a op b) % m er lik (a%m op b%m) % m for addisjon og multiplikasjon. Dermed kan du redusere inndataene før du kombinerer dem.

Addisjon, subtraksjon og multiplikasjon fungerer fint modulo en modul. Vanlig divisjon gjør derimot ikke det, og du trenger en modulær invers senere i kurset.

Definer MOD som en konstant i begynnelsen av løsningen. Én navngitt verdi er bedre enn å spre 1000000007 gjennom koden, der en skrivefeil kan skjule seg.

Du holder nå enorme opptellinger små med en primtallsmodul som 1e9+7. Reduser addisjon, subtraksjon og multiplikasjon i hvert trinn, ta hensyn til negative verdier, og spar divisjon til inverser. 🎯