Arbejd modulo et primtal

Svar i konkurrencer kan blive enorme, langt større end enhver heltalstype andre steder. Derfor beder opgaver om resultatet modulo et stort primtal, så tallene forbliver små. 🔢

Det primtal, du oftest vil se, er 1000000007, ofte skrevet som 1e9+7. Det er lige stort nok til at undgå sammenfald og lille nok til at passe i 64 bit.

Modulo-operatoren giver resten efter en division. Derfor er 17 % 5 lig med 2, fordi 17 giver resten 2, når det divideres med 5.

Du kan først addere og tage modulo til sidst eller tage modulo undervejs. Resten bliver den samme i begge tilfælde, så reducér ofte for at holde tallene små.

Den samme regel gælder for multiplikation: tag produktet modulo primtallet. Python håndterer store heltal indbygget, men modulo holder hver værdi lille og beregningen hurtig.

I en lang løkke skal du anvende % MOD ved hver iteration. Det forhindrer tallene i at vokse voldsomt og holder hver operation billig og forudsigelig.

Subtraktion kan give en negativ rest i mange sprog. Læg MOD til igen før den endelige modulo-operation, så resultatet ender i det ikke-negative område fra 0.

Godt nyt: Pythons % giver allerede et ikke-negativt resultat for et positivt modul. Derfor giver -1 % 7 resultatet 6, ikke -1, så du slipper for en ekstra korrektion.

Grundideen er: (a op b) % m er lig med (a%m op b%m) % m ved addition og multiplikation. Det lader dig reducere input, før du kombinerer dem.

Addition, subtraktion og multiplikation fungerer problemfrit modulo et tal. Almindelig division gør ikke, og senere på kurset får du brug for en modulær invers.

Definér MOD som en konstant i begyndelsen af din løsning. Én navngiven værdi er bedre end at sprede 1000000007 ud i koden, hvor en slåfejl kan gemme sig.

Du kan nu holde enorme tællere små med et primmodul som 1e9+7. Reducér addition, subtraktion og multiplikation ved hvert trin, pas på negative værdier, og gem division til inverser. 🎯