Ostatnia liczba potegi SPOJ pomocy!

Question

Tutaj jest moj kod, moim zdaniem, jest on poprawny. Dziala nawet dla duzych liczb. Jednak spoj pokazuje mi blad wykonania. Czy ktos moglby pomoc? Gdzie nie dostrzegam mojego błędu? Z góry dziękuje. 

#include <iostream>

using namespace std;
long long potega(long a, long b)
{
    if(b==0) return 1;
    else return potega(a, b-1)*a;
}

int main()
{
    int il_t;
    cin>>il_t;
    for(int i=0; i<il_t; i++)
   {
    long long  a, b;
    int pom;
    cin>>a>>b;
    pom=b%4;
    if(pom==0)
    {
        cout<<potega(a,4)%10<<endl;
    }
    else if(pom==1)
    {
        cout<<potega(a,1)%10<<endl;
    }
    else if(pom==2)
    {
        cout<<potega(a,2)%10<<endl;
    }
    else if(pom==3)
    {
        cout<<potega(a,3)%10<<endl;
    }
   }

    return 0;
}

 

Answer 1

Widzę że umiesz pisać algorytm potęgowania. Jednak to zadanie jest mega proste i nie na tym polega. Weź kartkę i rozpisz sobie liczby po kolei i zobacz czy jest może jakaś reguła. Jak odgadniesz tą regułę to będziesz się mega śmiał ;)

Comments

No ja wiem, nie chodzi o to co jest na dole? Przecież funkcja na gorze to nie caly program.

Answer 2

Witam,

zapewne problemem u Ciebie jest długość obliczeń. Komputery mimo dużej mocy obliczeniowej do przetwarzanie wielkich danych potrzebują określonej długości czasu. To może się nie podobać SPOJ'owi i nie zaakceptuje rozwiązania. Rozwiązując to zadanie polecam pójść drogą pośrednią tzn zauważyć pewne zależności dla ostatnich liczb a nie surowo liczyć wielkie potęgi. Np

dla 1 
Ostatnia liczba będzie 1
1^1 = 1 1^2 = 1 1^3 = 1
dla 5
Ostatnia liczba będzie 5
5^1 = 5 5^2 = 25 5^3 = 125
dla 6
Ostatnia liczba będzie 6
6^1 = 6 6^2 = 36 6^3 = 216

Dla innych liczb też można zauważyć pewne prawidłowości.

Comments

Rzeczywiście, spróbuje. Jednak dziwi mnie to lekko, bo w zamysle przecież ten program omija duże liczby, przeciez liczba trzy cyfrowa to pikus dla kompa ;)