For Last K Gene has posted the right Approach.
For First K
Hint : Logarithms log(N^N) = NlgN
On Tue, Oct 4, 2011 at 1:14 AM, Gene <gene.ress...@gmail.com> wrote:
> I have not done this, so I'm not sure. But there are some tricks.
>
> You can first break up the computation to exploit repeated squaring.
> Rather than n-1 multiplications, you can get away with log_2 n by
> computing
>
> n_1 = n^2
> n_2 = n_1^2
> n_3 = n_2^2
> so that n_i = n^{2^i}
> for i=1..N where n_N <= n and n_{N+1} > n
>
> Let b_i be the i'th bit of n.
>
> Then n^n = product_{ i | b_i = 1 } ( n_i )
>
> Now as you say you can't afford to do the full multiply. So you'll
> need two arbitrary precision multiplication algorithms keeping k
> digits of precision each. The first is easy. Compute n^n as above
> modulo 10^k (always throwing away higher order digits) to get the last
> k digits.
>
> The high order digits is the tricky part. I think the basic idea is
> to implement floating point yourself. I.e. keep k+some extra digits
> of mantissa plus an exponent to show where the decimal place is. The
> problem is you always need to keep enough extra digits beyond k to be
> sure rounding up won't affect to top k. There should be simple
> algorithm to determine when you can stop.
>
> Or you can take a chance and count on the fact that the probability of
> carry out is limited for each digit, so with about 30 extra digits the
> chances are pretty close to zero.
>
>
> On Oct 3, 8:18 pm, g4ur4v <gauravyadav1...@gmail.com> wrote:
> > can anyone please help me on how to approach this problem=>
> http://www.codechef.com/problems/MARCHA4
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
