As you can see, we used a conjugate to get rid of the number's irrationality. so (3+sqrt(5))^n=r-(3-sqrt(5))^n since 3-sqrt(5) is always less than 1 no matter what the value of n, then the integer value of (3+sqrt(5))^n=r-1 to avoid negative values, we used instead (r+999)%1000 Calculating the value of r by using fast exponentiation and multiplying it with x0,y0 (2x1 matrix of x0 y0) where x0=1 and y0=0. you get that it equals m[0][0] +m[1][1] But m[0][0] = m[1][1] so the answer is (2*m[0][0]+999)%1000
I hope i managed to help Sami On Aug 18, 1:07 pm, Saul Hidalgo <[email protected]> wrote: > Hi... > > I was trying to solve the problem Number(Round 1A). I read the Contest > Analysis, but... i do not undestand why do they calculate that. > > "return (2 * M_n[0][0] + 999) % 1000" > > Because, in this matrix (4) in the Costest Analysis, we have the > numbers an and bn. > > Why is it wrong? (an + bn*sqrt(5))%1000; > > Thanks =) > > -- > Saul Hidalgo --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
