PA05_POT - Czy umiesz potęgować SPOJ

pytanie zadane 7 lutego 2023 w SPOJ przez Tactykalier Nowicjusz (200 p.)

ile = int(input())
for i in range(ile):
    dane = input()
    b, potega = dane.split()
    potega = int(potega)
    b = int(b)
    a = pow(b,potega)
    print(a%10)

Witam, próbowałem już rozwiązać zadanie zawarte w temacie na wiele sposobów tak, aby zostało zaakceptowane przez sędziego. Jednak według SPOJa przekraczam limit czasu, czy ktoś wie w czym leży problem? Dziękuję za pomoc z góry.

komentarz 8 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

A i oczywiście tu masz klasykę o teorii liczb, praktycznie wszystkie podstawowe i nawet kilka zawansowanych algorytmów omówione: https://www.youtube.com/watch?v=abPEZKoTeZA

2 odpowiedzi

odpowiedź 7 lutego 2023 przez adrian17 Mentor (353,600 p.)

Jednak według SPOJa przekraczam limit czasu

ma rację :)

czy ktoś wie w czym leży problem?

Spójrz na treść zadania:

(1 ≤ a,b ≤ 1 000 000 000).

I zastanów się ile potrwa liczenie (albo jak duża będzie) liczba postaci miliard do potęgi miliard :)

komentarz 7 lutego 2023 przez Tactykalier Nowicjusz (200 p.)

ma to sens :)

komentarz 7 lutego 2023 przez Tactykalier Nowicjusz (200 p.)

biorę się za poprawki

komentarz 7 lutego 2023 przez Tactykalier Nowicjusz (200 p.)

a czy funkcja pow jest odpowiednia do tego zadania?

komentarz 8 lutego 2023 przez Tactykalier Nowicjusz (200 p.)

@adrian17, szczerze mówiąc dalej otrzymuję ten sam komunikat, prawdopodobnie dalej jeszcze czegoś nie ogarniam heh

ile = int(input())
if ile>=1 and ile<=10:
    for i in range(ile):
        dane = input()
        a, b = dane.split()
        a = int(a)
        b = int(b)
        if a>=1 and a<=1000000000 and b>=1 and b<=1000000000:
            wynik = pow(a,b)
            print(wynik%10)

komentarz 8 lutego 2023 przez Whiskey_Taster Pasjonat (15,610 p.)

Instrukcje warunkowe w tym wypadku są zbędne. W zadaniach tego typu nie należy przeprowadzać walidacji danych, bo z założenia są one poprawne.

Podpowiedź: wypisz sobie parę potęg kolejnych liczb od 1 do 10 i zobacz, czy widzisz jakąś sekwencję.

odpowiedź 8 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Jest taki algorytm, nazywa się szybkie potegowanie, który w logu umie wyliczyć wyrażenie a^b. Jest bardzo intuicyjny, https://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/

Korzystasz z tego, że a^x * a^y = a^(x+y). Można to próbować zapisać od dołu, ale rekurencyjnie jest łatwiej.