Problema
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
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.
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.