SPOJ czy umiesz potęgować? - przykład testów

Question

Próbuje rozwiązać to zadanie ze SPOJa, sposób jaki obrałam to:

-pobranie "podstawy" i "wykładnika" ( cin>>p>>w; )

-z potęgi podstawy biorę samą cyfrę jedności ( p = p%10; )

-Dla wykladnika 0, wynik bedzie zawsze = 1 ( if(w==0) wynik=1; )

- 0, 1, 5 i 6 wynik bedzie zawsze równy tej cyfrze.

- dla pozostałych cyfr rozpisuje na przypadki

( np. else if (p==2 && w%4==0) wynik=6;
        else if (p==2 && (w+1)%4==0) wynik=8;
        else if (p==2 && (w+2)%4==0) wynik=4;
        else if (p==2 && (w+3)%4==0) wynik=2;)

 

Wydawało mi się ze ten tok rozumowania jest na tyle prosty ze nie może "nie przejść". No a jednak.

Kiedy wpisuje losowe liczby wynik zgadza mi się z np obliczeniem na kalkulatorze.

Może ktoś z was rzuciłby mi jakieś przyklady testów (skrajnych liczb), które naprowadziłyby mnie na właściwe rozwiązanie?

Z góry dzięki! :)

Comments

A może przedstawisz treść zadania?

---

myślałam że przy spoj-u sensowniej bedzie podac tytuł zadania, ale proszę: 

Dla danych dwóch liczb naturalnych a i b, wyznaczyć ostatnią cyfrę liczby ab.

Zadanie
Napisz program, który:

• wczyta ze standardowego wejścia: podstawę a oraz wykładnik b,
• wyznaczy ostatnią cyfrę liczby ab,
• wypisze wynik na standardowe wyjście.

Wejście
W pierwszej linii wejścia znajduje się jedna liczba całkowia D (1≤D≤10), oznaczjąca liczbę przypadków do rozważenia. Opis każdego przypadku podany jest w jednym wierszu, zawierającym dwie liczby naturalne a i b oddzielone pojedynczym odstępem (spacją), takie, że (1 ≤ a,b ≤ 1 000 000 000).

Wyjście
Dla każdego przypadku z wejścia Twój program powinien wypisać (w osobnej linii dla każdego przypadku z wejścia) cyfrę jedności liczby abzapisanej dziesiętnie.

Przykład
Dla danych wejściowych:

2
2 3
3 3

poprawną odpowiedzią jest:

8
7

---

Ale spoj wywala błąd obliczeń? Zakładam że algorytm masz dobry bo widzę podobny jest na http://zapytaj.onet.pl/Category/006,003/2,17707157,Jak_wyznaczac_ostatnia_cyfre_potegi_liczby_naturalnej_o_bardzo_duzym_wykladniku.html

Chętne bym się tym zajął bo wydaje się łatwe ale nie mogę się uporać z moim zadaniem już trzeci wieczór (ETI07F1 - Igiełka) Chyba że się poddam to rzucę okiem na Twoje zadanie.

Answer 1

Hmm, no to spróbujmy, input:
2
1 1
1000000000 2

Output:
1
0

Answer 2

Rozumiem, że pomysł z tym algorytmem jest, jak się wydaje, właściwy i powinien zadziałać, ale czy nie lepiej byłoby tak po prostu: pobrać a i b, temp=a^b, wynik=temp%10? Mam nadzieję, że rozważysz moją propozycję.

Comments

A wyobrażasz sobie jak program policzy miliard do potęgi miliardowej?

---

Po prostu policzy, tu nie chodzi przecież o czas wykonania ani nic innego tylko o wynik

---

Nie, nie policzy to są za duże liczby. Właśnie cała trudność na tym polega. 

A poza tym są ograniczenia.

Limit czasu wykonania programu:	0.529s
Limit długości kodu źródłowego	5000B
Limit pamięci:	1536MB

---

Przepraszam, nie wiedziałem nic o tych ograniczeniach Można usuwać odpowiedzi?

---

Spoko nie mogłeś wiedzieć bo w treści tu tego nie było. Ale tak czy inaczej w wyniku dostajemy liczbę o 90 miliardach znaków tego największy chiński superkomputer nawet nie policzy przez rok czasu ;)

Kasować chyba nie można ale edytuj jak chcesz

Answer 3

Porzuciłem "Igiełke" bo szkoda nerwów na to zadanie i popatrzyłem dziś na potęgowanie.

Tak więc algorytm wygląda następująco.

Podstawa potęgowania - wystarczy brać ostatnią cyfrę. Następnym krokiem jest wypisać sobie tablicę wyników dla wszystkich podstaw. To jest łatwa sprawa.. Przykładowo dla liczby 2 to będzie tablica czteroelementowa (2,4,8,6). Zamieszczam poniżej link do moich wypocin w calcu jak zrobić taką tablicę. Jak mamy tablicę to dzielimy wykładnik-1 modulo liczba elementów tablicy dla danej potęgi. Wyjaśnię na przykładzie.  2^1004 Czyli obliczamy 1003 modulo 4 bo podstawa 2 ma okres 4. 1003 modulo 4 w pamięci można policzyć daje nam 3. Czyli wynikiem jest trzeci indeks w tablicy (liczymy od 0) czyli 6. I to tyle. Trochę może zagmatwane ale po przeanalizowaniu można samemu rozkminić.

Tabela https://i.imgur.com/EfWbRG4.png