Re: [obm-l] Power!

[Rodrigo Malta Schmidt <rodrigo.schmidt@xxxxxxxxxxxxx>]

Sim.

Voce quer calcular

a^(a^(a^(...a^a))) % 10000

Agora vamos chamar a^(a^(a^(...a^a))) de a^^(n) certo??? So para nao
complicar ainda mais as coisas.

Por inducao vemos que 

a^^(n) = a^(a^^(n-1))

Se a nao eh multiplo de 5 nem de 2 entao eh primo relativo de 10000,
certo??

Se a eh primo relativo de 10000, entao pelo teorema de Euler

a^^(n) = a^(a^^(n-1)%phi(10000)) (mod 10000)

phi(10000) = 2/5(10000) = 4000


a^^(n) = a^( a^^(n-1)%4000 ) (mod 10000)

Fazendo tudo de novo...

Queremos calcular...

a^^(n-1) % 4000

como mdc(a,4000)=1

a^^(n-1) = a^(a^^(n-2)%phi(4000)) % 4000

phi(4000) = 2/5(4000) = 1600

E por ai vai ate que voce chega em

a^^{k} mod 1 que eh 0

Depois eh so voltar fazendo algumas exponenciacoes.

Voce precisa de algumas iteracoes mas eh bem mais rapido do que fazer
todas as exponenciacoes originais.

Se nao me fiz entender, posso ser mais detalhista.

Ab,
Rodrigo


Vinicius José Fortuna wrote:
> 
> Pessoal,
> 
> Existe alguma forma fácil de se calcular os 4 primeiros dígitos de
> a^(a^(a^(...a^a))) (o 'a' aparece n vezes)
> Sendo que a não é múltiplo de 2 nem de 5
> 
> ????????????
> 
> Obrigado
> 
> Vinicius Fortuna
> 
> =========================================================================
> 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>
> =========================================================================
=========================================================================
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>
=========================================================================