Re: [obm-l] Re: Orientação para resolução

[Vinicius José Fortuna <ra992559@xxxxxxxxxxxxx>]

Uma maneira mais genérica de fazer esse cálculo seria utilizando "divisão 
e conquista" em que a potência é sempre dividida por dois. Assim:

(Sempre mod 100)

2^1000 = (2^500)^2
2^500 = (2^250)^2
2^250 = (2^125)^2
2^125 = 2.(2^62)^2
2^62 = (2^31)^2
2^31 = 2.(2^15)^2
2^15 = 2.(2^7)^2
2^7 = 2.(2^3)^2
2^3 = 8 

Agora é só substituir de trás pra frente.
As contas de quadrado mod 100 ficam fáceis se fizer assim:
x = 10a + b
x^2 = 100a^2 + 20ab + b^2
x^2 = 20ab + b^2 (mod 100)

e 20ab (mod 100) = ((ab mod 10).2 mod 10).10

Processando...
2^7 = 2.64 = 28
2^15 = 2.84 = 68
2^31 = 2.24 = 48
2^62 = 48^2 = 04
2^125 = 2.16 = 32
2^250 = 32^2 = 24
2^500 = 24^2 = 76
2^1000 = 76^2 = 76

Normalmente isso não dá muitas contas. 
É aproximadamente floor(log(n base 2)) operações de quadrado onde n é o 
expoente.

Até mais

Vinicius Fortuna


On Mon, 21 Jan 2002 ghaeser@zipmail.com.br wrote:

> >Quais são os últimos dois algarismos de 2^1000 ??
> 
> 
> Não sei resolver esse tipo de questão, mas como encontrei a resposta certa
> resolvi mandar a mensagem !!
> 
> Será que alguém poderia postar uma maneira mais fácil de obter essa resposta
> ??
> 
> 
> obs : as igualdades são todas mod 100
> 
> 2^10 = 24
> (2^10)^100 = 24^100 = (2^3*3)^100 = 
> 
> (2^10)^30*3^100 = 24^30*3^100 = (2^3*3)^30*3^100 =
> 
> (2^10)^9*3^130 = 24^9*3^130 = (2^3*3)^9*3^130 =
> 
> 2^27*3^139 = 2^30/8*3^139 = 24^3/8*3^139 = 12^3*3^139 = 
> 
> 4^3*3^142 = 64*3^142
> 
> analisando as potencias de 3 mod 100:
> 
> 3^1=3
> 3^2=9
> 3^3=27
> 3^4=81
> 3^5=43
> 3^6=29
> 3^7=87
> 3^8=61
> 3^9=83
> 3^10=49
> 
> 
> 
> 3^142*64=49^14*64*9
> 
> 
> analisando as potencias de 49 mod 100:
> 
> 49^1=49
> 49^2=01
> 49^3=49
> 49^4=01
> ..
> 49^14=01 mod 100
> 
> assim, temos que : 49^14*64*9 = 64*9 = 76 mod 100
> 
> Portanto os últimos dois algarismos de 2^1000 é 76
> conferindo :
> 
> 2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
> 
> 
> 
> "Mathematicus nascitur, non fit"
> Matemáticos não são feitos, eles nascem
> 
> 
> ------------------------------------------
> Use o melhor sistema de busca da Internet
> Radar UOL - http://www.radaruol.com.br
> 
> 
> 
> =========================================================================
> 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
> O administrador desta lista é <nicolau@mat.puc-rio.br>
> =========================================================================
> 

-- 
[     Vinicius José Fortuna      ]
[ vinicius.fortuna@ic.unicamp.br ]
[  Visite www.viniciusf.cjb.net  ]


=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================