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.

Método dos mínimos quadrados

Ainda sobre a prova de 2004 da seletiva da USP, agora no problema F: Estimando a Produção.

Se eu soubesse o que era o método dos mínimos quadrados antes de ler o problema eu ia ver isso e pensar “óbvio!”. Fazendo uma analogia, seria como um problema que possa ser resolvido com Dijkstra ser descrito por um grafo e pedindo o menor caminho a partir de um vértice para todos. Enfim… faltaram algumas aulas de matemática aí.

O problema é descaradamente a aplicação do método dos mínimos quadrados. Eu li isso, entendi a modelagem e tal, mas como resolver isso computacionalmente?? Não é trivial =/
Nesse link tem alguns métodos numéricos que mostram como fazer, mas sem pseudo-código nem nada… e pra mim que não conheço esses algoritmos fica difícil.

Em algum outro lugar vi que podia ser resolvido com o método de Newton ou algoritmo de Gauss-Newton, mas não olhei os detalhes deles ainda.

Largest Empty Circle

Sobre o problema I, da prova de 2004 da seletiva interna para a maratona de programação da USP, chamado Centro de Convenções.

Esse problema é um caso especial do “largest empty circle”, descrito aqui. Para resolver esse problema acho que tem que ser feito o seguinte:

Primeiro vc tem que gerar o diagrama de Voronoi do seu plano. Suponha que seu plano seja formado por um conjunto de n pontos: p1, p2, …, pn. Esse diagrama é uma divisão do plano em regiões de maneira que as arestas dessas regiões são formadas por pontos equidistantes de pi e pj. Cada vértice da região é um ponto equidistante de três ou mais pontos. Portanto, em cada região só existe um ponto pi, e aquela região contém todos os pontos que são mais próximos de pi do que de qualquer outro do plano.

Um diagrama de Voronoi pode ser construído com o algoritmo de Fortune (não achei trivial, por isso não implementei esse algoritmo =/ ).

Dado que a região foi construída, a maior circunferência que não contém nenhum pi terá o centro localizado em um dos vértices desse diagrama. Logo, basta percorrer a lista de vértices e verificar qual é a distância para os três (ou mais) pontos que definiram esse vértice.

A construção do diagrama é feita em O(n log n), o que é maior que o custo linear de percorrer os vértices para encontrar o centro do círculo procurado, logo, essa é a complexidade do algoritmo.

Texto

No meio da avalanche de mensagens sentimentais que eu recebo pela internet, algumas valem a pena… E essa é uma delas. Procurei pela autora e o blog dela é esse aqui. Não olhei muito bem o que tem por lá ainda, esse texto com certeza não foi publicado nesse blog. Mas enfim, com autoria certa ou não, a mensagem é bacana, e é o jeito que eu quero viver minha vida (talvez exceto pelo vinho do porto =P ).

Da minha precoce nostalgia
Maria Sanz Martins

Quando eu for bem velhinha, espero receber a graça de, num dia de domingo, me sentar na poltrona da biblioteca e, bebendo um cálice de vinho do Porto, dizer a minha neta:
– Querida, venha cá. Feche a porta com cuidado e sente-se aqui ao meu lado. Tenho umas coisas pra te contar.
E assim, dizer apontando o indicador para o alto:
– O nome disso não é conselho, isso se chama corroboração!
Eu vivi, ensinei, aprendi, caí, levantei e cheguei a algumas conclusões. E agora, do alto dos meus 82 anos, com os ossos frágeis, a pele mole e os cabelos brancos, minha alma é o que me resta saudável e forte. Por isso, vou colocar mais ou menos assim:
É preciso coragem para ser feliz. Seja valente. Siga sempre seu coração. Para onde ele for, seu sangue, suas veias e seus olhos também irão. E satisfaça seus desejos. Esse é seu direito e obrigação. Entenda que o tempo é um paciente professor que irá te fazer crescer, mas a escolha entre ser uma grande menina ou uma menina grande, vai depender só de você. Tenha poucos e bons amigos. Tenha filhos. Tenha um jardim. Aproveite sua casa, mas viaje, vá a Fernando de Noronha, Rio de Janeiro, a Barcelona e a Austrália. Cuide bem dos seus dentes. Experimente, mude, corte os cabelos. Ame. Ame pra valer, mesmo que ele seja o carteiro. Não corra o risco de envelhecer dizendo “ah, se eu tivesse feito…” Tenha uma vida rica de vida. Vai que o carteiro ganhe na loteria – tudo é possível, e o futuro é imprevisível.
Viva romances de cinema, contos de fada e casos de novela. Faça sexo, mas não sinta vergonha de preferir fazer amor.

E tome conta sempre da sua reputação, ela é um bem inestimável. Porque sim, as pessoas comentam, reparam, e se você der chance elas inventam também detalhes desnecessários.
Se for se casar, faça por amor. Não faça por segurança, carinho ou status.
A sabedoria convencional recomenda que você se case com alguém parecido com você, mas isso pode ser um saco! Prefira a recomendação da natureza, que com a justificativa de aperfeiçoar os genes na reprodução, sugere que você procure alguém diferente de você. Mas para ter sucesso nessa questão, acredite no olfato e desconfie da visão. É o seu nariz quem diz a verdade quando o assunto é paixão.
Faça do fogão, do pente, da caneta, do papel e do armário, seus instrumentos de criação. Leia. Pinte, desenhe, escreva. E por favor, dance, dance, dance até o fim, se não por você, faça-o por mim.
Compreenda seus pais. Eles te amam para além da sua imaginação, sempre fizeram o melhor que puderam, e sempre farão.
Cultive os amigos. Eles são a natureza a nosso favor e uma das formas mais raras de amor.
Não cultive as mágoas – porque se tem uma coisa que eu aprendi nessa vida é que um único pontinho preto num oceano branco deixa tudo cinza.
Era só isso minha querida. Agora é a sua vez. Por favor, encha mais uma vez minha taça e me conte: como vai você?