Ontem eu fiquei em terceiro no POWTOW:
Esse problema pede para calcular o Knuth double up-arrow (que parece nome de posição sexual né? "oi benzinho vamos fazer o knuth double up-arrow?"). Mas na verdade isso é só a notação que o Knuth inventou para potências de potências. Tipo 5^^3 = 5^5^5, e 7^4=7^7^7^7.
O primeiro instinto é usar o teorema de Euler:
a^totient(n) = 1 (mod n)
...maaas isso só funciona quando a e n são primos entre si. Então na verdade a pegadinha do problema é descobrir um jeito de generalizar esse teorema para a e n quaisquer.
Eu achei duas maneiras: a maneira lenta é usando o teorema chinês do resto, a maneira rápida fica como exercício para o leitor
Acho que não vai dar para pegar o primeiro lugar nesse não, os tempos já estão bem apertados e tirar 0.01s vai ser bem difícil.
Nenhum comentário:
Postar um comentário