Lavorare modulo un numero primo
Sommare e moltiplicare restando nel modulo
Lavorare modulo un numero primo è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Perché usare il modulo
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 modulo più famoso
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.
MOD = 1000000007Cosa significa il modulo
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.
print(17 % 5) # 2L'addizione resta nel modulo
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.
total = (a + b) % MODAnche la moltiplicazione resta nel modulo
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.
prod = (a * b) % MODRidurre dopo ogni passaggio
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.
ans = (ans * i) % MODLa sottrazione può diventare negativa
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.
diff = (a - b + MOD) % MODIl modulo pratico di Python
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.
print(-1 % 7) # 6Il modulo si distribuisce sulle operazioni
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.
La divisione è l'eccezione
Addizione, sottrazione e moltiplicazione funzionano correttamente con un modulo. La semplice divisione, invece, no: più avanti nel corso servirà un inverso modulare.
Definire MOD una sola volta all'inizio
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.
MOD = 10**9 + 7Verifica rapida
Perché bisogna aggiungere MOD prima di applicare il modulo a una sottrazione?
Riepilogo
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. 🎯
Domande Frequenti
La lezione «Lavorare modulo un numero primo» è gratuita?
Sì — il testo completo di «Lavorare modulo un numero primo» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Lavorare modulo un numero primo»?
Sommare e moltiplicare restando nel modulo Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Lavorare modulo un numero primo»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Lavorare modulo un numero primo
- Esponenziazione modulare rapida
- Inverso modulare tramite Fermat
- nCr con fattoriali precalcolati