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)
para o caso geral n!
seja n = x ( mod 10)
e a = [n/10] ( maior inteiro menor ou igual )
temos n! ( mod 10 ) = 1^a*2^a*3^a*4^a*5^a*6^a*7^a*8^a*9^a*0^a*(x!)
como queremos o ultimo algarismo nao nulo denovo jogamos fora 2,5,0 e resovemos da mesma maneira que acima. Veja que se x >=5, devemos descartar o 2 e 5 de x! tb.
-Auggy
From: "Qwert Smith" <[EMAIL PROTECTED]> Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] Digitos de 1000! Date: Mon, 22 Mar 2004 18:21:31 -0500
O problema e que 1000 e um pouquinho maior que 50... sao 168 primos < 1000, por isso to tentando ver se tem uma outra saida
-Auggy
btw... para n=50 e simples e direto ver que 50!= 30414093201713378043612608166064768844377641568960512000000000000
com 12 zeros e ultimo algarismo nao nulo tb 2
From: Johann Peter Gustav Lejeune Dirichlet <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Re: [obm-l] Digitos de 1000!
Date: Mon, 22 Mar 2004 19:40:00 -0300 (ART)
Ainda me lembro de como eu achei para n=50.Sao 10 zeros no final (acho).Alias essa foi um questao da OPM....Temos que eliminar as fontes de zeros.Foiu o que fiz ai...
1*1*3*4*1*6*7*8*9*1 11*6*13*14*3*16*17*18*19*2 21*11*23*12*1*26*27*28*29*3 31*16*33*34*7*36*37*38*39*4 41*21*43*22*9*46*47*48*49*1
Os 1,11,21,31,41 nao importam. Agora e meio porrada mas da para andar bem....Depois eu tento escrever decentemente, mas levem isso como alguma ajuda...
So uma coisa: tenha um pouco mais de consideraçao pela sua lingua natal...
Fabiano Sant'Ana <[EMAIL PROTECTED]> wrote:
não tenho a minima idéia de como resolver isso sem usar "BrutalForce"(ou seja, calcular os números 1 a 1)...
[]s Fabiano ----- Original Message ----- From: Cláudio (Prática) To: [EMAIL PROTECTED] Sent: Monday, March 22, 2004 12:08 PM Subject: [obm-l] Digitos de 1000!
Oi, pessoal:
Já que o assunto é potências de primos que dividem n!, aqui vai um bonitinho:
1) (clássico) Por quantos zeros termina a representação decimal de 1000!
2) (menos conhecido e mais difícil) Qual o último algarismo não nulo na representação decimal de 1000!
3) (generalização) Qual o último algarismo não nulo de n!? Dica não muito útil: é sempre par se n > 1.
[]s, Claudio.
--- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com/). Version: 6.0.624 / Virus Database: 401 - Release Date: 15/03/04
TRANSIRE SVVM PECTVS MVNDOQVE POTIRI
CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE
Fields Medal(John Charles Fields)
--------------------------------- Yahoo! Mail - O melhor e-mail do Brasil. Abra sua conta agora!
_________________________________________________________________
Check out MSN PC Safety & Security to help ensure your PC is protected and safe. http://specials.msn.com/msn/security.asp
========================================================================= 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 =========================================================================
_________________________________________________________________
Is your PC infected? Get a FREE online computer virus scan from McAfee® Security. http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963
========================================================================= 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 =========================================================================
