499. Czy umiesz potęgować [PA05_POT]

Ja zauważyłem że ostatnia cyfra przy potegowaniu powtaża się co 4 potege. Może też byc cały czas taka sama ale na pewno każda cyfra powtaża się co czwartą potęgę. Więc wymyśliłem tak:

#include <iostream>

using namespace std;
int a, b, ile;
int reszta;
int main()
{
    cin >> ile;
    for (int i=1; i<=ile; i++)
    {
        cin >> a >> b;
        reszta=b%4;
        switch(reszta)
        {
        case 0:
        {
            cout << (a*a*a*a)%10 << endl;
        }
        break;
        case 1:
        {
            cout << a%10 << endl;
        }
        break;
        case 2:
        {
            cout << (a*a)%10 << endl;
        }
        break;
        case 3:
        {
            cout << (a*a*a)%10 << endl;
        }
        break;
        }
    }

cout << reszta << endl;

return 0;
}

Na kompilatorze działa, a SPOJ mówi o będnej odpowiedzi. Widzi ktoś błąd w moim rozumowaniu?

@forestek1
Zauważyłeś dobrze ale nie zauważyłeś że np. milion^4 nie policzy bo wyjdziesz po za obszar nawet unsigned long long inta, którego i tak powinineneś użyć bo w tym zadaniu wartości danych testowych są bardzo duże. Podpowiem tak to da się rozwiązać na warunkach ALE też trzeba coś ZAUWAŻYĆ, najlepiej w tym zadaniu użyć szybkiego potęgowania modularnego (bodajże na khanacademy jest to dobrze wyjaśniona zasada) Jak dobrze poszukasz to znajdziesz nawet gotową implementacje którą sam testowałem i przechodziła, Nie przeraź się ale większość dobrych implementacji potęgowania modularnego, używa przesunięcia bitowego. Piszę trochę podpowiedziami ale nie chcę Ci popsuć satysfakcji z samodzielnie rozwiązanego zadania. Co do twojego kodu to zacząłbym od początku. Ew. możesz poszukać na starym forum wątku z tym zadaniem link do starego forum -> pl.spoj.com/forum-old146

EDIT: Taka uwaga na przyszłość jeśli wrzucasz swój kod na forum, to go sformatuj żeby był czytelniejszy (nikomu nie chce się czytać niesformatowanych kodów, jeśli korzystasz z (codeblocksa użyj wtyczki format use AStyle)), umieść z tagach a najlepiej to wrzuć na ideone.com35 i podaj tylko link do swojego kodu. od razu ktoś będzie mógł przeprowadzić testy.

Ta, poniższa, linia jest "bardzo błędna" i nie na miejscu

No i częściowo to co napisał tycjan, [to co dotyczyło a], ale czy potrzebujesz "całego a"? Może wystarczy Ci tylko jego mała ociupinka?

@narbej @forestek1
To miała być ta podpowiedź, Można rzec że jeśli chodzi o postać bitową danego wyrażenia to komputerowi jest nazwijmy "obojętne" (w przypadku tego zadania) czy liczy milion^2 czy np 100^2.

Jeżeli nawet wcześniejszą podpowiedź zrozumiałem, to tego co napisałeś nie tylko, że nie rozumiem, to nawet nie staram się zrozumieć Co ma piernik do wiatraka. Całe szczęście, że @forestek1 chyba już zaliczył to zadanie bez naszej pomocy, A to co chciałeś powiedzieć, to:
pewnie to, że:
2^10 == 1 << 10
czy
2^30 == 1 << 30
ale bez przesady z tymi milionami i nawet, jeżeli komputerowi jest to zupełnie obojętne, [w tym zadaniu] to programiście już nie powinno.
Powtarzam, że zupełnie nie rozumiem tego co chcesz powiedzieć. Akurat w tym zadaniu reprezentacja bitowa, powiedziałbym, że zupełnie nie ma znaczenia. Tylko takie, że komputer zawsze tak liczy, na bitach Oczywiście, że to zadanie można zrobić, korzystając z szykiego potęgowania modularnego, [sam tak zrobiłem w pierwszej wersji] ale można też tak jak właśnie zrobił to @forestek1 - po poprawieniu drobnych błędów w jego kodzie, więc nie powinieneś radzić mu, aby zaczynał od początku..

Na początek int to za mało, na wejściu mogą się pojawić liczby do miliarda więc potrzebujesz longa. Po drugie algorytm do napisania od nowa, ten tu jest chyba za wolny

No obleci, nie taki on znowu wolny
Ale tak jak napisałeś [@sig] int za mało - long long
scanf("%lld %lld", a, b)//& &

@bunker96
Dodatkowo pomyśl nad np takim testem:
2
1000000000002 2
10000000000000003 2
itd

@bunker96
modulo10 (1000000000002 ** 2) = ?
modulo10 (100000000002 ** 2) = ?
modulo10 (10000000002 ** 2) = ?
modulo10 (1000000002 ** 2) = ?
itd
Czy potrzebujesz całej "a" czy wystarczy jej mały kawałek a może jeszcze mniej a, może wystarczy tylko ociupinka a?

Tylko mi zwraca zle wartosci np tam gdzie powinno byc 4 wychodzi 1.
Edit: Dobra zadanie zrobione ale nadal nie rozumiem dlaczego jak dzialalem na duzej podstawie potegi to wyniki zle podawalo. A i jeśli macie jakies rady odnosnie porawy wydajnosci to by mnie bardzo ucieszylo

Pytanie ile będzie wynosić ostatnia cyfra (bo tylko jej potrzebujemy) z 10 * cokolwiek, 30 * cokolwiek itd? W zasadzie potęgowanie w tym zadaniu jest opcjonalne, można sobie "gotowce" przygotować.

No tak zrobilem i dziala. Ale dlaczego nie dzialalo jak uzywalem calej liczby? Przekroczylem jakis limit? Edit Dzieki narbej

Tak. Np.:
1000000**4 = 1000000000000000000000000L < 2**64 = 18446744073709551616L
10000000000000000000**4 = 10000000000000000000000000000000000000000000000000000000000000000000000000000

max unsigned long long = 2**64 -1 = 18446744073709551615
max unsigned int = 2 ** 32 -1 = 4294967295

Mógł by ktos pomoc? Na testach ten kod działa poprawnie ale "sąd" widzi gdzieś nadal błąd

 <code>

#include<iostream>
#include<math.h>

using namespace std;
int n,*b,*p,*w;

int potega(int p,int w)
{
    if(w==1) return 1;
    else
       return p*potega(p,w-1);
}

int main()
{
    cin>>n;
    if ((n<=1)||(n>=10))return 0;
    b=new int[n];
    p=new int[n];
    w=new int[n];
    for(int i=0;i<n;i++)
    {
        cin>>p[i]>>w[i];
        w[i]++;
    }
        for(int i=0;i<n;i++)
    {
        if(potega(p[i],w[i])>9)
        {
            cout<<(((int)potega(p[i],w[i])))-(((int)potega(p[i],w[i])/10)*10)<<endl;
        }
        else cout<<potega(p[i],w[i])<<endl;
    }




    return 0;
}
</code>

Jesli sie ktos to zrozumie to gratuluje xD "Czytanie kodu jest jak wąchanie bąków - nie jest tak źle jak jest własny."

Przeczytaj wszystkie albo chociaż część komentarzy w tym wątku, jak zrozumiesz to gwarantuję, na pewno będziesz miał AC. Natomiast twój kod, bez czytania widać, że twój kod jest do ... bani, ale sam zobacz:
http://ideone.com/Wgw3Kz253
Testy z zadania, to zupełne minimum z minimum, służą bardziej do "mentalnego" zrozumienia zadania a nie do całkowitego stwierdzenia poprawności kodu. Powinieneś wymyślać swoje własne, trudniejsze testy, a tu możesz sprawdzać ich poprawność [dla dowolnych danych]:

http://www.wolframalpha.com/input/?i=mod+%2810000000000000003^2%2C+10%29154

Zastanawiam się co tu może być jeszcze źle, na moich testach już praktycznie wszystko działa

   <juz znalazlem blad>

Wiesz, że istnieje takie coś jak wyszukiwanie?( Dokładniej taka lupa w prawym górnym rogu). Ten temat był przetwarzany wiele razy.
Znalazłem test, dla którego twój program daje niepoprawny wynik:
1
333 32323213
Twój out: 1
Poprawny out: 3
Poza tym twój kod jest strasznie nieczytelny - zbyt dużo warunków. Popraw ten kod z pomocą tego linka: cyfra jedności potęgi267.
Wystarczy ułożyć poprawny algorytm z podanych informacji.

PS. Na przyszłość nie twórz nowych wątków, tylko dołączaj się do już istniejących.
PS 2. Zobacz ile już było wątków: wątki

Czyli, aby wyznaczyć resztę z potęgowania muszę wyznaczyć dla każdej cyfry warunek, tak ?

Jeżeli dobrze rozumiem "wyznaczyć resztę", to tak.

Ale czy moje rozumienie ma tu jakieś znaczenie? Chyba lepiej po prostu napisać program realizujący Twoją myśl i zobaczyć co z niego wyjdzie

Panowie... poległem, po przeczytaniu tych wszystkich postów i dosłownie dziesiątek prób zmian tego kodu doszedłem do tej wersji i mimo, że przy każdej sprawdzanej przeze mnie kombinacji cyfr wynik wychodzi dobry, to jednak SPOJ nie akceptuje mojego kodu.

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int a, t;
    double b, c;
    
    cin >> t;
    
    for(int i = 0 ; i < t ; i++)
    {
            cin.clear();
            cin.sync();
            
            cin >> a >> b;
            
            a = a%10;
            c = pow(a, b);
            int d  = (int)(c);
            
            cout << d%10 << endl;
    }
    return 0;
}