Обсуждение @ 1587. Летающая свинья @ Timus Online Judge

Need help(+)

Послано Aram Shatakhtsyan 11 янв 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 янв 2008 17:53

Use long arithmetics :)

Re: Need help(+)

Послано Aram Shatakhtsyan 17 янв 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 [KNU] 18 янв 2008 20:54

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

Re: Need help(+)

Послано Chmel_Tolstiy 18 янв 2008 22:52

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

Re: Need help(+)

Послано Denis Koshman 20 июл 2008 19:08

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

Re: Need help(+)

Послано Nisarg Shah 1 янв 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(+)

Послано SevenEleven [Tartu U] 1 янв 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 сен 2009 20:25

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

Обсуждение задачи 1587. Летающая свинья