exponenciação Modular Rápida
Calcule potências com pow(a, b, m).
exponenciação Modular Rápida é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
O problema da potência
Frequentemente, você precisa elevar um número a um expoente enorme, tudo sob um módulo. Multiplicar um fator de cada vez levaria etapas demais. ⚡
A abordagem ingênua é lenta demais
Um loop que multiplica b vezes executa em O(b) etapas. Com um expoente próximo de um bilhão, isso ultrapassa o limite de tempo antes mesmo de terminar.
for _ in range(b): r = r * a % MODEleve ao quadrado para avançar mais rápido
O truque é elevar ao quadrado: a elevado à 8ª potência equivale a elevar ao quadrado três vezes. Cada operação de elevar ao quadrado dobra o expoente, permitindo alcançar potências enormes em poucas etapas.
Leia o expoente em binário
Todo expoente é uma soma de potências de dois, sua forma binária. Portanto, você só multiplica pelas potências da base correspondentes aos bits definidos, ignorando as demais.
# 13 = 1101 -> a^8 * a^4 * a^1Verifique o bit menos significativo
Observe b & 1 para verificar o bit menos significativo. Se ele for 1, incorpore a base atual ao resultado acumulado antes de continuar.
if b & 1: result = result * base % MODDesloque e eleve ao quadrado a cada rodada
Após cada bit, eleve a base ao quadrado e desloque o expoente uma posição para a direita. O loop executa apenas cerca de 30 a 60 vezes para qualquer entrada realista.
base = base * base % MOD
b >>= 1Reúna tudo
Comece o resultado com 1 e, em seguida, repita enquanto o expoente for positivo. Essa ideia de exponenciação rápida também é chamada de exponenciação binária ou exponenciação por quadratura.
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1Executa em tempo logarítmico
Como cada rodada divide o expoente pela metade, o custo é O(log b). Isso transforma um bilhão de multiplicações em aproximadamente trinta, bem dentro de qualquer limite.
O Python oferece pow
Você raramente precisa escrever o loop: a função integrada pow(a, b, m) do Python faz a exponenciação modular rápida com a velocidade do C puro.
print(pow(2, 100, MOD))Por que isso será importante em breve
A exponenciação rápida é a base do inverso modular usando Fermat, que você verá a seguir. Domine-a agora, e a divisão sob um módulo ficará fácil.
Observe primeiro a base
Reduza a base com base % MOD antes do loop. Caso contrário, uma base já maior que o módulo aumentaria todas as etapas de elevação ao quadrado.
base = a % MODVerificação rápida
Qual é a complexidade da exponenciação modular rápida?
Revisão
Agora você pode elevar números a expoentes enormes em O(log b) usando quadratura e leitura de bits. No Python, basta chamar pow(a, b, m) e continuar. 🚀
Perguntas Frequentes
A aula “ exponenciação Modular Rápida” é grátis?
Sim — o texto completo de “ exponenciação Modular Rápida” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “ exponenciação Modular Rápida”?
Calcule potências com pow(a, b, m). Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “ exponenciação Modular Rápida”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Trabalhando Módulo um Primo
- exponenciação Modular Rápida
- Inverso Modular por Fermat
- nCr com Fatoriais Pré-calculados