Inverso Modular por Fermat

Adição, subtração e multiplicação se comportam bem sob um módulo, mas a divisão comum não. Você não pode simplesmente dividir e calcular o resto. ⚠️

A solução é o inverso modular: dividir por x se torna multiplicar pelo inverso de x. Assim, a / b módulo m se transforma em a multiplicado pelo inverso de b.

O inverso de x é o número que, multiplicado por x sob o módulo, resulta em 1. Ele desempenha o papel de 1/x na aritmética comum.

Um inverso existe somente quando x não compartilha nenhum fator com m. Usar um módulo primo como 1e9+7 garante que todo x diferente de zero tenha um.

O pequeno teorema de Fermat afirma que, para um primo p, x elevado a p menos 1 é congruente a 1, desde que x não seja múltiplo de p.

Separe um fator x, e o restante deverá ser o seu inverso. Portanto, o inverso de x é x elevado a p menos 2, calculado módulo p.

Esse expoente é enorme, então use a exponenciação rápida da lição anterior. No Python, uma chamada a pow faz todo o trabalho por você.

Para calcular a dividido por b sob o módulo, multiplique a pelo inverso de b. O resto será exatamente o quociente verdadeiro módulo p.

Não existe inverso de 0, pois nada multiplicado por zero resulta em um. Evite dividir por um valor que se reduza a zero sob o módulo.

Cada inverso obtido pelo teorema de Fermat é uma exponenciação rápida, portanto custa O(log p) de tempo. Isso é barato para algumas divisões, mas se acumula quando você faz milhões delas.

Quando precisar de muitos inversos, pré-calcule-os com uma passagem linear inteligente, em vez de chamar pow para cada elemento. Você usará essa técnica a seguir, com nCr.

Qual potência fornece o inverso modular sob um primo?

Agora você divide sob um módulo primo multiplicando pelo inverso modular, obtido como x elevado a p menos 2 por meio de pow. Apenas nunca calcule o inverso de zero. ✅