PA05_POT - Czy umiesz potęgować SPOJ

Question

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.

Comments

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

Answer 1

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 :)

Comments

ma to sens :)

---

biorę się za poprawki

---

a czy funkcja pow jest odpowiednia do tego zadania?

---

@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)

 

---

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ę.

Answer 2

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.

Comments

To ja tylko zaznaczę że... nie, to nie zadziała.

---

Dziwne, napisałem i weszło na 100 na Spoju

---

quick pow(podstawa,wykladnik,mod)

i oczywiście mod 10, bo ostatnia cyfra