Thanks Sami.
Now, i have some new questions.
About the Solution A:
1. I undestand this ecuation:
α^n == an + bn*sqrt(5); (Alpha)^n
but, i do not sure that:
β^n == an - bn*sqrt(5); (Beta)^n
Are both an and bn the same? How can i see it?
2. Suppose that
(Alpha) == 3+sqrt(5);
==>
(Alpha)^n == an + bn*sqrt(5);
And then ==>
(Alpha)^(n+1) == (3+sqrt(5)) * (an + bn*sqrt(5));
Fine, now ... similar to the Solution A...
a_(n+1) == 3*an + 5*bn;
b_(n+1) == (3*bn + an)*sqrt(5);
Now, the target is find an and bn, if i found an and bn with the
ecuation (4), why is it wrong??
(an + bn*sqrt(5))%1000; //It should be right.
About the Solution B:
1. In the step/equation (6). How can i write the matrix?
Thanks again :):)
On Wed, Aug 19, 2009 at 9:12 AM, Sami Ghawi <[email protected]> wrote:
>
>
> 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
> >
>
--
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
-~----------~----~----~----~------~----~------~--~---
