Lavorare modulo un numero primo

Le risposte delle gare possono diventare enormi, oltre la capacità di qualunque tipo intero. Perciò i problemi chiedono il risultato modulo un numero primo grande, così da mantenere piccoli i valori. 🔢

Il numero primo che incontrerà più spesso è 1000000007, scritto spesso come 1e9+7. È abbastanza grande da evitare collisioni, ma abbastanza piccolo da rientrare in 64 bit.

L'operatore modulo restituisce il resto dopo una divisione. Quindi 17 % 5 è 2, perché 17 lascia un resto pari a 2 quando viene diviso per 5.

Può sommare prima e applicare il modulo alla fine, oppure applicarlo man mano. Il resto è lo stesso in entrambi i casi, quindi riduca spesso i valori per mantenerli piccoli.

La stessa regola vale per la moltiplicazione: calcoli il prodotto modulo il numero primo. Python gestisce nativamente gli interi grandi, ma applicare il modulo mantiene ogni valore piccolo e rende le operazioni rapide.

In un ciclo lungo, applichi % MOD a ogni iterazione. In questo modo evita che i numeri crescano a dismisura e mantiene ogni operazione economica e prevedibile.

La sottrazione può produrre un resto negativo in molti linguaggi. Aggiunga nuovamente MOD prima del modulo finale, così il risultato rientra nell'intervallo sicuro dei valori non negativi.

Una buona notizia: l'operatore % di Python restituisce già un risultato non negativo quando il modulo è positivo. Quindi -1 % 7 dà 6, non -1, evitando una correzione aggiuntiva.

L'idea fondamentale è che (a op b) % m è uguale a (a%m op b%m) % m per l'addizione e la moltiplicazione. Questo consente di ridurre gli operandi prima di combinarli.

Addizione, sottrazione e moltiplicazione funzionano correttamente con un modulo. La semplice divisione, invece, no: più avanti nel corso servirà un inverso modulare.

Definisca MOD come costante all'inizio della soluzione. Un unico valore con un nome è preferibile a disseminare 1000000007 nel codice, dove un errore di battitura può passare inosservato.

Perché bisogna aggiungere MOD prima di applicare il modulo a una sottrazione?

Ora sa mantenere piccoli i conteggi enormi usando un modulo primo come 1e9+7. Riduca addizione, sottrazione e moltiplicazione a ogni passaggio, gestisca i valori negativi e riservi la divisione agli inversi. 🎯