ostatnia liczba

Jest to zadanie ze SPOJ i nie mam pojęcia jak dokończyć, a muszę wyznaczyć ostatnią cyfrę liczby wyniku z potęgowania. Może wy mnie jakoś nakierujecię bym dał rade rozwiazać to.. ? Wynik np. 27 i ma byc widoczna tylko 7.

#include <iostream>
#include<math.h>
using namespace std;
int main()
{
    int a,b,ile;
    cin>>ile;
    for(int i=1; i<=ile; i++)
    {
            cin>>a>>b;
            cout<<pow(a,b)<<endl;
    }
    return 0;
}

modulo z 10. Zawsze da Ci ostatnia liczbe

27 % 10 daje 7

Ale od razu ostrzegam, że jak będziesz potęgował "na pałę" i dopiero potem brał ostatnią cyfrę, to nie zaliczysz wszystkich testów. Trzeba pewną rzecz zauważyć odnośnie reszty z dzielenia przez 10.

a ten kod który napisałem jest ok? Tylko muszę Modulo zastosować czy bardziej funkcje pow wyrzucić i zamienić czymś innym?

A zauważ jak zachowuje się cyfra jedności w potęgach.
Jaką cyfrę jedności ma np. 6ⁿ i 46ⁿ albo 96ⁿ
Jak zachowuje się cyfra jedności np. podczas 7¹, 7², 7³, 7⁴, 7⁵, 7⁶ itd.

Ostatnia cyfra iloczynu 235769863*3792577 jest identyczna z ostatnią cyfrą iloczynu 3*7 (mnożymy ostatnie cyfry). Analogiczna reguła jest prawdziwa dla dowolnych liczb.

    #include <stdio.h>
     
    int main() 
      {
       unsigned T,a,b;
       for(scanf("%u",&T);T--;printf("%c\n",(10*(b&3)+(a%10))["0161656161012345678901496569410187456329"])) scanf("%u%u",&a,&b);
       return 0;
      } 

Myślę, że przydatna będzie funkcja

int multiply(int n,int m)
{
    return ((n % 10)*(m % 10)) % 10;
}

tym razem wykazał mi sędzia "przekroczono limit czasu"

#include <iostream>
using namespace std;
long int potega(int p, int w)
{
    if (w==0) return 1;
    else return p*potega(p,w-1);
}
int main()
{
    int ile,p,w;
    cin>>ile;
    for(int i=1; i<=ile; i++)
    {
        cin>>p>>w;
        cout<<potega(p,w)%10<<endl;
    }
}

No a co ci ma wypisać? Nie przeczytałeś ze zrozumieniem żadnego postu w tym temacie chyba. Nadal potęgujesz te liczby, do tego jeszcze rekurencyjnie o_O Nie zrozumiałeś tego co bodans napisał?
123456789123456789 ma taką samą ostatnią cyfrę jak 99. Nie trzeba wykonywać całego takiego mnożenia żeby poznać wynik. Jakbym sie ciebie zapytał jaka jest ostatnia cyfra liczby:
123456789123456789*1234567890 to też byś to najwpierw wszystko wymnożył dokładnie?

W ten sposób tego nie zrobisz, wychodzą takie wyniki że nie mieszczą się w żadnej dostępnej w c(++) zmiennej. Python "twierdzi" że np 8 do potęgi 100 ma 91 cyfr, a tym danym wejściowym przecież daleko do maksymalnych.

Dodam jeszcze, że komunikat sędziego był inny niż "przekroczono limit czasu". Ten kod ma błąd składniowy, więc programu się nie uruchomi. Trochę Ci podpowiem, zamiast

        cin>>p>>w;
        cout<<potega(p,w)%10;<<endl;

daj

        cin>>p>>w;
        p = p % 10;
        cout<<potega(p,w)%10<<endl;

Może już wystarczyć, jeśli nie, to podrasuj funkcję potega.

Kod wkleiłem taki jak podałem "Wam". Nie mam w zwyczaju oszukiwać, zwłaszcza osób które proszę o rade ale to moje stanowisko nie każdy musi taki być.

<img src=http://naforum.zapodaj.net/thumbs/ab6fdf5acde5.jpg alt=hosting zdjęć zapodaj.net />

Ale już dość, zbytnio oddaliłem się od tematu który mnie interesuje.

Najprostsze (najszybsze to już podałem) co powinno przejść to:

        cin>>p>>w;
        cout<<((int)pow(p%10,4+w%4))%10<<endl;

Żeby ten kod dostał przekroczono limit czasu, starczy usunąć nadmiarowy średnik z couta (po %10). Bez tego daje błąd kompilacji.

A teraz już Ci zarzucę kłamstwo, założyłem konto na SPOJ-u, wysłałem Twój kod i zobaczyłem to: .

masz racje bogdans dałęm inny kod na forum w ostatniej linijce wkradł mi sie ";" a na spoju go w kodzie nie mam tutaj jest błąd

_13th_Dragon napisał(a):

Najprostsze (najszybsze to już podałem) co powinno przejść to:

        cin>>p>>w;
        cout<<((int)pow(p%10,w%4))%10<<endl;

P=2 w=4 wynik powinien być 6, Twoj kod daje 1

        w = w % 4;
        if(w == 0) 
        {
            w = 4;
        }
        cout << ((int)pow(p%10,w))<< endl;

Istnieje cykl, trzeba bylo policzyc sobie kilka pierwszych wyników a potem sprawdzić kiedy cykl sie rozpoczyna od nowa. W problemach algorytmicznych trzeba czasami pomyśleć, a nie robić na pałę.

import sys
matrix = [
    ["1\n","1\n","1\n","1\n"],
    ["2\n","4\n","8\n","6\n"],
    ["3\n","9\n","7\n","1\n"],
    ["4\n","6\n","4\n","6\n"],
    ["5\n","5\n","5\n","5\n"],
    ["6\n","6\n","6\n","6\n"],
    ["7\n","9\n","3\n","1\n"],
    ["8\n","4\n","2\n","6\n"],
    ["9\n","1\n","9\n","1\n"],
    ["0\n","0\n","0\n","0\n"],
]

test_num = int( sys.stdin.readline() )
for test_num in xrange(0, test_num):
    input = sys.stdin.readline().split(' ')
    sys.stdout.write( matrix[(int(input[0])-1)%10][(int(input[1])-1)%4] )

Albo po prostu

test_num = int(raw_input())
for test_num in xrange(0, test_num):
    input = raw_input().split(' ')
    a = int(input[0])
    b = (int(input[1])-1)%4+1
    x = 1
    for i in xrange(0, b):
        x *= a
        x %= 10
    print x