Tutte le sfide
Media 0 risolte 0% di accettazione

Esponenziazione modulare

Calcola una base elevata a un esponente, modulo un numero, con l'esponenziazione rapida.

Cosa imparerai

  • Elevare un numero a una potenza enorme in O(log exponent) passi
  • Ridurre ogni valore intermedio per evitare l'overflow
  • Gestire esponente 0 e modulo 1

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

Esempio 1
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.

Esempio 2
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.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.