*Conjugate pairs* are the key. Here's a detailed explanation... http://www.necessaryandsufficient.net/2008/07/google-codejam-numbers/
Hope that helps. On Tue, Apr 19, 2011 at 6:35 AM, utsav sabharwal <[email protected]>wrote: > Indeed the solution mentioned on > http://code.google.com/codejam/contest/dashboard?c=32016#s=a&a=2 is > pretty awesome but that lays stress on mathematical concepts over > advanced programming logic.... which means that we have to be good > mathematicians first to be a good programmer... > > Nah I dont agree....I have a different solution... > > Rule 1: Square-roots can be calculated by division while division can > be done by multiplication... (moreover multiplication can be done by > addition but that wont be required here) > > Rule 2: If seen from a different perspective each digit of the result > is calculated by a set pattern or simple terms a formula > > P.S.: We just need to develop the formula for first and second digit > of the result for n (where n<=2000000000) in terms of multiplying or > adding the digits of the question > > Comment: In this approach value of n or the max size of a variable > wont be a constraint. Not just this but any calculation can be done > up-to infinite limits, the only constraint shall be time and space. > > Utsav > > > > On Mon, Apr 18, 2011 at 9:52 PM, Luke Pebody <[email protected]> > wrote: > > "You can't". You'd need a lot of memory and a lot of time to work out the > > integer part of this large a value. However, you don't need to work out > the > > entire integer part. You can, for instance find the last two digits of > > 2301^45392884746345 without working out all of the digits. See the > "Contest > > Analysis" at http://bit.ly/21iXp4 > > > > On 18 Apr 2011 17:11, "raulrag" <[email protected]> wrote: > >> How will u handle such a large input of 2000000000 in C . > >> What different techniques can be used to find (3+root(5) ) ^N for such > >> a large input > >> > >> -- > >> 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. > >> > > > > -- > > 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. > > > > -- > 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. > > -- 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.
