Re: [obm-l] Digitos de 1000!

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 22.03.04 22:45, Qwert Smith at lord_qwert@hotmail.com wrote:

> 
> Acabo de ver que na verdade nao e nada dificil e nao precisa saber quantos e
> quais sao os pirmos < 1000, ja que e desnecessario fatorar o fatorial :)
> 
> Queremos (1000!/10^429) mod 10 basta escrever
> 1*2*3*...*11*12*13*...*988*989*990*998*999*1000 ( mod 10 ) ->
> 1^100*2^100*3^100*4^100*5^100*6^100*7^100*8^100*9^100*0^100 ( mod 10 )
> que isso da 0 ja sabiamos mas como queremos o ultimo  digito nao nulo vamos
> descartar 2,5 e 0
> sobra entao:
> 1^100*3^100*4^100*6^100*7^100*8^100*9^100 =
> 1^99*1*2^99*2*3^99*3*...*8^100*9^99*9
> mas como 9^99 = -1^99,  7^99 = -3^99, etc da pra ver que os termos se anulam
> com excecao do 8 , logo sobra 1*3*4*6*7*9*8^100, e nem precisa de muito
> braco pra chegar em 2 (mod 10)
> 
Acho que precisa de muito braco sim, pois  1*3*4*6*7*9*8^100 =
9239995188653228887313669642624939338529460633668686832885533078271473575726
495299247890497536 == 6 (mod 10).

Agora falando serio. A sua solucao estah incorreta porque o que voce
realmente quer eh 1000!/10^249 (mod 10).
Ou seja, voce quer eliminar 249 fatores iguais a 2 e 249 fatores iguais a 5
de 1000! e depois reduzir o que sobrar mod 10.
Ao eliminar todos os numeros terminados em 0, 2 e 5 do produto de 1000!, de
fato voce estarah retirando todos os 249 fatores 5. Soh que, junto com eles,
voce estarah eliminando muito mais do que apenas 249 fatores 2, e este muito
mais infelizmente afeta o valor do ultimo algarismo nao nulo de 1000!.


[]s,
Claudio.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================