Problema
Calcola base^exponent mod modulus. L'esponente può arrivare a 10^18, quindi moltiplicare per base tante volte è impossibile; usa invece l'esponenziazione rapida per quadrati successivi: guarda le cifre binarie dell'esponente, eleva al quadrato la base a ogni passo e moltiplicala nel risultato quando la cifra è 1. Così bastano circa 60 passi per qualsiasi esponente di questo esercizio.
Implementa modular_exponentiation(base, exponent, modulus).
Riduci base modulo modulus all'inizio e dopo ogni moltiplicazione. Poiché modulus ≤ 10^9, il prodotto di due valori ridotti è minore di 10^18 e sta in un intero con segno a 64 bit.
Input
base: la base.
exponent: la potenza a cui elevare la base.
modulus: il numero rispetto a cui calcolare il resto.
Output
Restituisci base^exponent mod modulus, un valore da 0 a modulus − 1. Considera base^0 uguale a 1 per qualsiasi base, 0 compreso, quindi con esponente 0 la risposta è 1 mod modulus.
Vincoli
0 ≤ base ≤ 10^18
0 ≤ exponent ≤ 10^18
1 ≤ modulus ≤ 10^9
Esempi
Input:
base = 3
exponent = 13
modulus = 50
Output atteso:
expected = 23
Input:
long long base = 3;
long long exponent = 13;
long long modulus = 50;
Output atteso:
long long expected = 23;
Input:
long base = 3;
long exponent = 13;
long modulus = 50;
Output atteso:
long expected = 23;
Spiegazione
3^13 = 1 594 323, e 1 594 323 = 50 × 31 886 + 23, quindi la risposta è 23.
Input:
base = 2
exponent = 10
modulus = 1000
Output atteso:
expected = 24
Input:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;
Output atteso:
long long expected = 24;
Input:
long base = 2;
long exponent = 10;
long modulus = 1000;
Output atteso:
long expected = 24;
Spiegazione
2^10 = 1024, e 1024 mod 1000 = 24.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Esamina l'esponente una cifra binaria alla volta, partendo dalla meno significativa.
Suggerimento 2
A ogni passo eleva al quadrato la base e moltiplicala nel risultato quando il bit corrente è 1.
Suggerimento 3
Inizializza il risultato a 1 % modulus, così con modulo 1 ottieni 0.
Complessità attesa
tempo O(log exponent), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.