Sobre o módulo da divisão de números grandes

Motivado pelo seguinte problema: https://br.spoj.pl/problems/DIOFANTO/

Então, eu li esse problema e bolei uma solução toda bonitinha pra ele usando combinatória. Só tava faltando implementar e eu mal sabia que era isso que ia me causar toda a dor de cabeça.

Eu estou implementando um algoritmo e em certo ponto preciso fazer a seguinte conta:

(a!/b!) mod p

Em que a e b são números cujo fatorial não cabe em uma variável, p é um primo e p é maior que a e b. Como proceder?

Obviamente não posso calcular o fatorial antes, fazer a divisão e depois tirar o módulo. Mesmo um algoritmo que tenta ir simplificando a fração à medida que o fatorial é calculado não funciona. E o módulo do quociente não é o quociente dos módulos (Não acredita? Teste com p = 7, a = 5 e b = 3).

O que fazer então? Bom, as seguintes propriedades vão ajudar:

a.b (mod p) = (a mod p)(b mod p) mod p
a / b = a.b-1

a-1 (mod p) existe se mmc(a, p) = 1

Agora a gente pode usar essas coisas pra fazer o seguinte:

(a/b) mod p = ab-1 mod p = (a mod p)(b-1 mod p) mod p

Por sorte (?) b e p são primos entre si, já que p é primo e b é menor que p, e podemos calcular o módulo do seu inverso. Pra fazer isso, tem que desenvolver a equação (eu quero encontrar o x):

b-1 = x (mod p)
b-1b = xb (mod p)
xb = 1 (mod p)
xb – 1= qp
xb – qp = 1 
Então tudo se resume a encontrar o x e q que resolvem a última expressão. Isso pode ser feito com o algoritmo estendido de Euclides.
Acho que já escrevi demais… vou tentar implementar isso agora.

One thought on “Sobre o módulo da divisão de números grandes”

Comments are closed.