Aritmetica modulare
In molti casi, non ci interessa il valore assoluto di un calcolo, ma piuttosto il risultato di quel calcolo modulo
m (ovvero il resto ottenuto dividendo il risultato per m).Curiosamente, utilizziamo già nella quotidianità il concetto di aritmetica modulare. Quando guardiamo l’orologio per sapere che ora è, non ci importa quante ore siano passate dall’inizio dell’anno (o addirittura dal Big Bang), ma solo l’ora corrente del giorno. In pratica, stiamo considerando il numero di ore passate dall’inizio dell’anno modulo
12 o 24, a seconda del formato che usiamo. Man mano che il tempo avanza, l’orologio passa da 0 a 1, poi a 2, 3, …, fino ad arrivare a 11, e poi torna a 0. Questo ciclo si ripete in maniera infinita man mano che il tempo scorre. I numeri sul quadrante vanno sempre da 0 a 11. Data una quantità arbitraria di ore trascorse dall’inizio dell’anno h, possiamo sapere l’ora del giorno con h % 12 (il resto di h diviso per 12).
Se vogliamo considerare solo l’ultima cifra di un numero, possiamo immaginare una sorta di “orologio” con 10 posizioni - 0, 1, 2, … 9, che rappresentano tutte le cifre possibili. Aggiungendo 1 a un numero, la sua ultima cifra aumenta di 1 fino a arrivare a 9; dopodiché, aggiungendo un altro 1, l’ultima cifra ritorna a 0. Dato un numero qualunque
n, possiamo scoprirne l’ultima cifra calcolando n % 10 (il resto di n diviso per 10).Se invece ragioniamo in termini di bit (0 e 1), possiamo pensare a un “orologio” con appena 2 posizioni: 0 e 1. Se aggiungiamo 1 a 0, otteniamo 1. Se invece aggiungiamo 1 a 1, torniamo a 0. Per un numero binario qualunque
n, l’ultimo bit si ottiene con n % 2 (il resto di n diviso per 2).In sostanza, l’aritmetica modulare non è altro che un orologio con
m posizioni (ad esempio m = 12 per le ore, m = 10 per le cifre, m = 2 per i bit). m può essere qualsiasi numero e, in alcuni problemi, occorre calcolare il risultato modulo un grande numero primo come . Questo valore di solito è scelto per garantire che i calcoli siano effettivamente eseguiti e non eludibili.Addizione modulo m
Quando sommiamo due numeri
a e b, talvolta ci interessa soltanto il risultato modulo m. Ad esempio, se vogliamo l’ultima cifra della somma di a e b, ci interessa il risultato modulo 10. Ma possiamo semplificare ulteriormente il calcolo prendendo prima a e b modulo m (cioè l’ultima cifra di entrambi i numeri, in questo caso) e poi sommarli, calcolando infine il risultato modulo m. Questo rende i calcoli molto più semplici: res = (a % m + b % m) % m:Sottrazione modulo m
Possiamo interpretare la sottrazione di
b da a modulo m come far “tornare indietro” l’orologio di b posizioni a partire dal tempo a. Ad esempio, se riportiamo indietro l’orologio da 5 di 2 ore, (5 - 2) % 12 = 3. Se lo riportiamo indietro di 7 ore, (5 - 7) % 12 = -2 % 12 = 10. Anche se b fosse maggiore di m, potremmo comunque prendere prima la parte modulo m: (21 % 10 - 18 % 10) % 10 = (1 - 8) % 10 = 3:In alcuni linguaggi (come Python), l’operatore di resto
% restituisce sempre un valore positivo. In altri linguaggi (come C++), invece, potrebbe non essere così. Perciò, in quei casi, se il risultato è negativo, bisogna aggiungere m (ad esempio aggiungere 12 a -2 per ottenere 10). È come far avanzare l’orologio di un giorno intero, senza cambiare l’ora mostrata.Moltiplicazione modulo m
Quando moltiplichiamo due numeri modulo
m, possiamo equivalentemente prendere il risultato modulo m. Se m è 10, è come estrarre l’ultima cifra del prodotto di due numeri:Divisione modulo m
La divisione risulta più complicata rispetto alle altre operazioni. Pensando sempre all’ultima cifra, se dividiamo 28 per 7 otteniamo 4, quindi l’ultima cifra del risultato è 4. Tuttavia, se consideriamo solo l’ultima cifra di 28 (cioè 8) e l’ultima cifra di 7 (cioè 7), non è affatto ovvio come ricavare 4 dividendo questi due numeri. È comunque possibile effettuare la divisione modulo
m tramite il teorema di Eulero. Una spiegazione più dettagliata è disponibile qui: https://cp-algorithms.com/algebra/module-inverse.htmlSfida: Calcolare la potenza modulo m
Il problema consiste nel calcolare , dove
x, n e m sono forniti in input.Input
L’input contiene tre interi
x, n (1 ≤ n ≤ ) e m (1 ≤ x, m ≤ ).Output
Il programma deve stampare il risultato di .
Esempi
Input | Output |
2 6 10 | 4 |
3 2 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB