Discussion @ 1587. Flying Pig @ Timus Online Judge

Need help(+) 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(+) Victor Barinov (TNU) 16 Jan 2008 17:53

Use long arithmetics :)

Re: Need help(+) 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. (+) Orlangur 18 Jan 2008 20:54

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

Re: Need help(+) Chmel_Tolstiy 18 Jan 2008 22:52

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

Re: Need help(+) Denis Koshman 20 Jul 2008 19:08

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

Re: Need help(+) 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(+) Ignorance 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(+) 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