Discussion @ 1587. Flying Pig @ Timus Online Judge

Need help(+)

Posted by Aram Shatakhtsyan 11 Jan 2008 22:39

I don't understand, how it is possible to get the answer
for the test
50000
3 3 3 3 ... 3

3^50000 has length around 23856.

Re: Need help(+)

Posted by Victor Barinov (TNU) 16 Jan 2008 17:53

Use long arithmetics :)

Re: Need help(+)

Posted by Aram Shatakhtsyan 17 Jan 2008 19:36

How do it fast, so it can pass the time limit?
Maybe there are some trick there. Long multiplication
takes very long time, to do it 50000 times.

O(log(50000)) multiplications are enough. (+)

Posted by Orlangur [KNU] 18 Jan 2008 20:54

See http://www.algolib.narod.ru/Math/IndianPow.html if you understand Russian.

Re: Need help(+)

Posted by Chmel_Tolstiy 18 Jan 2008 22:52

I used just long by short (< 2^63) multiplication.

Re: Need help(+)

Posted by Denis Koshman 20 Jul 2008 19:08

Calculate it as ((3^2)^2 * 3)^2 * 3 for 3^11.

Re: Need help(+)

Posted by Nisarg Shah 1 Jan 2009 14:57

For calculating product, do we have to see how many consecutive numbers are same so as to calculate product of them by logarithmic power method? Because I see no other way to use the power method of logarithmic time...

Re: Need help(+)

Posted by SevenEleven [Tartu U] 1 Jan 2009 16:16

Note, that given "an integer not exceeding 3 in absolute value"

Edited by author 01.01.2009 16:16

Re: Need help(+)

Posted by marius dumitran 1 Sep 2009 20:25

x = 3^50000
does x have length 23856 or 23857?
does it start in 115 and end in 761000001?

Discussion of Problem 1587. Flying Pig