Todos os desafios
Médio 0 resolvidos 0% de aceitação

Exponenciação Modular

Calcule a base elevada ao expoente, módulo um número, usando exponenciação rápida.

O que você vai aprender

  • Elevar um número a uma potência enorme em O(log exponent) passos
  • Manter todo valor intermediário reduzido para evitar estouro
  • Tratar expoente 0 e módulo 1

Problema

Ver original (inglês)

Calcule base^exponent mod modulus. O expoente pode chegar a 10^18, então multiplicar por base esse número de vezes é impossível; use a exponenciação rápida (exponenciação por quadrados): percorra os dígitos binários do expoente, eleve a base ao quadrado a cada passo e multiplique-a no resultado quando o dígito for 1. Isso leva cerca de 60 passos para qualquer expoente deste problema.

Implemente modular_exponentiation(base, exponent, modulus).

Reduza base módulo modulus logo no início e depois de cada multiplicação. Como modulus ≤ 10^9, o produto de dois valores já reduzidos fica abaixo de 10^18 e cabe em um inteiro de 64 bits com sinal.

Entrada

base: a base.

exponent: a potência à qual a base é elevada.

modulus: o número pelo qual se tira o resto.

Saída

Retorne base^exponent mod modulus, um valor de 0 a modulus − 1. Considere base^0 igual a 1 para qualquer base, inclusive 0, então a resposta para expoente 0 é 1 mod modulus.

Restrições

0 ≤ base ≤ 10^18

0 ≤ exponent ≤ 10^18

1 ≤ modulus ≤ 10^9

Exemplos

Exemplo 1
Entrada:
base = 3
exponent = 13
modulus = 50

Saída esperada:
expected = 23
Entrada:
long long base = 3;
long long exponent = 13;
long long modulus = 50;

Saída esperada:
long long expected = 23;
Entrada:
long base = 3;
long exponent = 13;
long modulus = 50;

Saída esperada:
long expected = 23;

Explicação

3^13 = 1 594 323, e 1 594 323 = 50 × 31 886 + 23, então a resposta é 23.

Exemplo 2
Entrada:
base = 2
exponent = 10
modulus = 1000

Saída esperada:
expected = 24
Entrada:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;

Saída esperada:
long long expected = 24;
Entrada:
long base = 2;
long exponent = 10;
long modulus = 1000;

Saída esperada:
long expected = 24;

Explicação

2^10 = 1024, e 1024 mod 1000 = 24.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Olhe o expoente um dígito binário por vez, começando pelo menos significativo.

Dica 2

Eleve a base ao quadrado a cada passo e multiplique-a no resultado quando o bit atual for 1.

Dica 3

Comece o resultado em 1 % modulus, para que módulo 1 dê 0.

Complexidade esperada

tempo O(log exponent), espaço extra O(1)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.