Discussion @ 1587. Flying Pig @ Timus Online Judge

Aram Shatakhtsyan Need help(+) [8] // Problem 1587. Flying Pig 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.

Victor Barinov (TNU) Re: Need help(+) [2] // Problem 1587. Flying Pig 16 Jan 2008 17:53

Use long arithmetics :)

Aram Shatakhtsyan Re: Need help(+) [1] // Problem 1587. Flying Pig 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.

Orlangur [KNU] O(log(50000)) multiplications are enough. (+) // Problem 1587. Flying Pig 18 Jan 2008 20:54

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

Chmel_Tolstiy Re: Need help(+) [4] // Problem 1587. Flying Pig 18 Jan 2008 22:52

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

Denis Koshman Re: Need help(+) [3] // Problem 1587. Flying Pig 20 Jul 2008 19:08

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

Nisarg Shah Re: Need help(+) [2] // Problem 1587. Flying Pig 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...

SevenEleven [Tartu U] Re: Need help(+) [1] // Problem 1587. Flying Pig 1 Jan 2009 16:16

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

Edited by author 01.01.2009 16:16

marius dumitran Re: Need help(+) // Problem 1587. Flying Pig 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