[C++] Potenza di potenza
Devo risolvere il seguente problema
Descrizione del problema
Conveniamo di chiamare ennesima superpotenza di 2 il valore di 2^2n. Ad esempio la terza superpotenza di 2 è $2^(2^3) = 2^8 = 256$. Si chiede di calcolare la ennesima superpotenza di 2 modulo m.
Dati di input
Il file di input contiene due interi: n (0 <= n <= 10^5) ed m (2 <= m <= 10^4).
Dati di output
Il risultato richiesto dal problema.
Esempio:
n = 93329 k = 816, ris = 256
Il problema è che non riesco a calcolarlo senza andare in overflow.
Ho pensato, se n fosse uguale a 10
$ 2^(2^10) % m = (2^(2^5) % m * 2^(2^5)%m)%m $
Solo che con certi valori di m, con la moltiplicazione vado comunque in overflow
Descrizione del problema
Conveniamo di chiamare ennesima superpotenza di 2 il valore di 2^2n. Ad esempio la terza superpotenza di 2 è $2^(2^3) = 2^8 = 256$. Si chiede di calcolare la ennesima superpotenza di 2 modulo m.
Dati di input
Il file di input contiene due interi: n (0 <= n <= 10^5) ed m (2 <= m <= 10^4).
Dati di output
Il risultato richiesto dal problema.
Esempio:
n = 93329 k = 816, ris = 256
Il problema è che non riesco a calcolarlo senza andare in overflow.
Ho pensato, se n fosse uguale a 10
$ 2^(2^10) % m = (2^(2^5) % m * 2^(2^5)%m)%m $
Solo che con certi valori di m, con la moltiplicazione vado comunque in overflow
Risposte
[NOTA: mi viene illeggibile, leggo 22n, 223=28=256 che per me non ha senso]
Sei sicuro di doverlo calcolare? Rivediti magari un po' di aritmetica modulare.
Sei sicuro di doverlo calcolare? Rivediti magari un po' di aritmetica modulare.
"Rggb":
[NOTA: mi viene illeggibile, leggo 22n, 223=28=256 che per me non ha senso]
Sei sicuro di doverlo calcolare? Rivediti magari un po' di aritmetica modulare.
Ho fixato. Come mi chiede il problema devo calcolare il modulo di $ 2^(2^n) % m $. Quindi, non so se c'è un modo per trovare il modulo senza calcolare tutta la potenza
Se $k$ è il periodo di $2$ in $(ZZ_m, *)$ allora una qualsiasi potenza $2^n \mod m = 2^{sk+r} \mod m = 2^r$. Per risolvere il tuo problema calcolerei quindi per prima cosa il periodo $k$ di $2$ e poi calcolerei il resto tra $2^n$ e $k$ per vedere a quale potenza corrisponde.
"apatriarca":
Se $k$ è il periodo di $2$ in $(ZZ_m, *)$ allora una qualsiasi potenza $2^n \mod m = 2^{sk+r} \mod m = 2^r$. Per risolvere il tuo problema calcolerei quindi per prima cosa il periodo $k$ di $2$ e poi calcolerei il resto tra $2^n$ e $k$ per vedere a quale potenza corrisponde.
Cosa intendi per periodo?
Ciao!
Per risolvere il problema, considera che 2^n= m^x+y.
Quindi basta calcolare x come parte intera di (2*ln(n))/(ln(m)), e successivamente calcolare il resto tra y e m.
Per risolvere il problema, considera che 2^n= m^x+y.
Quindi basta calcolare x come parte intera di (2*ln(n))/(ln(m)), e successivamente calcolare il resto tra y e m.
"Omega":
Ciao!
Per risolvere il problema, considera che 2^n= m^x+y.
Quindi basta calcolare x come parte intera di (2*ln(n))/(ln(m)), e successivamente calcolare il resto tra y e m.
y cosa rappresenta?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo