Trabalhando Módulo um Primo

As respostas de competições podem crescer enormemente, muito além de qualquer tipo inteiro usado em outros contextos. Por isso, os problemas pedem o resultado módulo um primo grande, para manter os números pequenos. 🔢

O primo que você verá com mais frequência é 1000000007, geralmente escrito como 1e9+7. Ele é grande o bastante para evitar colisões e pequeno o bastante para caber em 64 bits.

O operador módulo fornece o resto após uma divisão. Portanto, 17 % 5 é 2, porque 17 deixa resto 2 quando dividido por 5.

Você pode somar primeiro e calcular o módulo no final, ou calcular o módulo à medida que avança. O resto será o mesmo de qualquer forma, portanto reduza os valores com frequência para mantê-los pequenos.

A mesma regra vale para a multiplicação: calcule o produto módulo o primo. O Python lida nativamente com inteiros grandes, mas calcular o módulo mantém cada valor pequeno e torna a execução mais rápida.

Em um loop longo, aplique % MOD a cada iteração. Isso impede que os números cresçam demais e mantém cada operação barata e previsível.

A subtração pode produzir um resto negativo em muitas linguagens. Adicione MOD novamente antes do módulo final para que o resultado fique no intervalo seguro de 0 a MOD - 1.

Boas notícias: o % do Python já retorna um resultado não negativo quando o módulo é positivo. Assim, -1 % 7 fornece 6, não -1, e você não precisa fazer uma correção adicional.

A ideia central é: (a op b) % m é igual a (a%m op b%m) % m para adição e multiplicação. Isso permite reduzir as entradas antes de combiná-las.

Adição, subtração e multiplicação funcionam de forma simples sob um módulo. A divisão comum, porém, não funciona assim, e você precisará de um inverso modular mais adiante neste curso.

Defina MOD como uma constante no início da sua solução. Um único valor nomeado é melhor do que espalhar 1000000007 pelo código, onde um erro de digitação pode passar despercebido.

Por que adicionar MOD antes de calcular o módulo de uma subtração?

Agora você mantém contagens enormes pequenas usando um módulo primo como 1e9+7. Reduza a adição, a subtração e a multiplicação a cada etapa, cuide dos valores negativos e deixe a divisão para os inversos. 🎯