Esponenziazione modulare rapida
Calcolare potenze con pow(a, b, m)
Esponenziazione modulare rapida è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 2 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.
Il problema delle potenze
Spesso è necessario elevare un numero a un esponente enorme, sempre lavorando modulo un certo valore. Moltiplicare un fattore alla volta richiederebbe troppi passaggi. ⚡
L'approccio ingenuo è troppo lento
Un ciclo che moltiplica b volte richiede O(b) passaggi. Con un esponente vicino al miliardo, si supera il limite di tempo prima ancora di terminare.
for _ in range(b): r = r * a % MODElevare al quadrato per procedere più velocemente
Il trucco è l'elevazione al quadrato: a elevato all'ottava è uguale a ((a al quadrato) al quadrato) al quadrato. Ogni elevazione al quadrato raddoppia l'esponente, consentendo di raggiungere potenze enormi in pochi passaggi.
Leggere l'esponente in binario
Ogni esponente è una somma di potenze di due, cioè la sua forma binaria. Quindi moltiplichi solo per le potenze della base corrispondenti ai bit impostati, saltando le altre.
# 13 = 1101 -> a^8 * a^4 * a^1Controllare il bit meno significativo
Osservi b & 1 per verificare il bit meno significativo. Se vale 1, inserisca la base corrente nel risultato accumulato prima di proseguire.
if b & 1: result = result * base % MODTraslare ed elevare al quadrato a ogni iterazione
Dopo ogni bit, elevi la base al quadrato ed esegua uno shift a destra sull'esponente di una posizione. Il ciclo esegue solo circa 30-60 iterazioni per qualsiasi input realistico.
base = base * base % MOD
b >>= 1Mettere tutto insieme
Imposti result su 1, poi esegua un ciclo finché l'esponente è positivo. Questa idea di esponenziazione rapida è chiamata anche esponenziazione binaria o esponenziazione per quadrati successivi.
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1Richiede tempo logaritmico
Poiché ogni iterazione dimezza l'esponente, il costo è O(log b). Un miliardo di moltiplicazioni diventa così circa trenta, ampiamente entro qualsiasi limite.
Python mette a disposizione pow
Raramente è necessario scrivere il ciclo personalmente: la funzione integrata pow(a, b, m) di Python esegue l'esponenziazione modulare rapida alla velocità del C puro.
print(pow(2, 100, MOD))Perché sarà utile tra poco
La potenza rapida è alla base dell'inverso modulare di Fermat, che incontrerà nella prossima lezione. La impari ora e la divisione con un modulo diventerà semplice.
Controllare prima la base
Riduca la base con base % MOD prima del ciclo. Una base già maggiore del modulo farebbe altrimenti crescere ogni passaggio di elevazione al quadrato.
base = a % MODVerifica rapida
Quanto è veloce l'esponenziazione modulare rapida?
Riepilogo
Ora sa elevare numeri a esponenti enormi in O(log b) usando i quadrati e leggendo i bit. In Python, chiami semplicemente pow(a, b, m) e proceda. 🚀
Impara Python con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 30
- Lezioni
- 120
Domande Frequenti
La lezione «Esponenziazione modulare rapida» è gratuita?
Sì — il testo completo di «Esponenziazione modulare rapida» è 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 «Esponenziazione modulare rapida»?
Calcolare potenze con pow(a, b, m) 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 2 di 4.
Quanto tempo richiede la lezione «Esponenziazione modulare rapida»?
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