http://code.google.com/codejam/contest/dashboard?c=32016#s=aa=2
2010/5/19 Adrian kri...@gmail.com
The only solution I can think of is to use the binomial theorem
(http://en.wikipedia.org/wiki/Binomial_theorem) to expand
(3+sqrt(5))^n . Then you only need to take into the account the terms
let @=3+sqrt(5)
so @^n = (3+sqrt(5))^n =(an+bn*sqrt(5))
@^(n-1)=(3+sqrt(5))*(an+bn*sqrt(5))
so an+1=3an+5bn
bn+1=an+3bn
so [an bn]= A [an-1 bn -1]
= A^n [a0 b0] where a0=1 and b0=0
where a= [ 3 5,1 3]
calculate an and bn in each step and devide it by 1000 for next an
