Jakiego algorytmu użyć do rozwiązania zadania?

0

Witam.
Mam takie oto zadanie: http://ideone.com/3BPcEo (nie jest to spoj ani nic podobnego, żeby nie było).
Zastanawiam się jakiego algorytmu użyć, żeby było jak najszybciej? Myślałem nad alg. Karatsuby, ale może jest coś szybszego?
Jak przechowywać tę dużą liczbę z wejścia? Podzielić ją na mniejsze i wpakować w tablicę?
Proszę o sugestie i pomysły.
Pozdrawiam i dziękuję :) .

PS: Mogę tu użyć potęgowania modularnego?

1

Na szybko:
http://pl.wikipedia.org/wiki/Algorytm_szybkiego_pot%C4%99gowania

plus użyj jakiejś gotowej implementacji bignumów np. z biblioteki standardowej javy lub napisz własną (jeśli nie ma jej w twoim jezyku, bo własna najprawdopodobniej będzie wolniejsza).
http://docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html

Modulo raczej nic Ci nie pomoże, bo i tak musisz mieć koncowy wynik n^m (żeby policzyć sumę cyfr).

(Mogę się mylić, bo to "rozwiązanie" jest w połowie drogi miedzy prysznicem a wyjściem do znajomych, jak wrócę to się zgłębię).

1

Rozważałeś reprezentację liczby potęgowanej jako wielomianu ? A potęgowania jako mnożenia wielomianów z wykorzystaniem szybkiej transformaty Fouriera?

http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/lectures/lect0423.txt

0

Dziękuję za podpowiedzi i jeśli mogę to zapytam jeszcze o jedno:
Czy ten kod do big num: http://ideone.com/pH8YBD się nada?
Znalazłem go w jednej z moich książek z listingami kodu.

0

Skoro odpowiedź (w zadaniu) ma być: 14848102 oznacza to że należy obstawiać że ilość cyfr wyniku będzie 14848102/5 czyli około 2969620 (niecałe 3 mln).
Big num też się nie wyrobi.

0

Więc co proponujesz _13th_Dragon?

0

To samo co podał @yarel zwłaszcza pierwsze zdanie jego postu.

0

Czyli co szybkie potęgowanie i alg. Karatsuby mogły by być?

1

Masz wybór różnych algorytmów:
Standardowo - O (N^2)
Karatsbua - O(N^1.58..)
Fast Fourier Transformation - O(n log n)
Schonhage-Strassen - O(n log n loglog n)

Ja bym się zastanowił nad tym, którego implementacja będzie najbardziej dla Ciebie korzystna. Nie z punktu widzenia rozwiązania problemu, ale wiedzy jaką zdobędziesz próbując zrozumieć i zaimplementować coś innego niż trywialne rozwiązanie w O(N^2).

1 użytkowników online, w tym zalogowanych: 0, gości: 1