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 � <[EMAIL PROTECTED]>
> =========================================================================
=========================================================================
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 � <[EMAIL PROTECTED]>
=========================================================================
