SPOJ - Czy umiesz potęgować - Optymalizowanie

0

Witam, mam(y) takie zadanie:

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 ab zapisanej dziesiętnie.

Domyślamy się, że licznie wszystkiego to raczej słaby pomysł i zauważamy, ze ostatnie cyfry powtarzają się co ileś.

2^1 = 2 +
2^2 = 4 ++
2^3 = 8 +++
2^4 = 16 ++++
2^5 = 32 +
2^6 = 64 ++
2^7 = 128 +++
2^8 = 256 ++++
2^9 = 512 +
2^10 = 1024 ++
2^11 = 2048 +++
2^12 = 4096 +++

Zatem, pomysł jest taki aby utworzyć listę takiej jednej serii (w tym przypadku byłoby to {2,4,8,6}), a później "skakać" po jej elementach i zwiększając licznik aż dojdziemy do wartości potęgi z wejścia

dostajemy 2 11 (2^11)

licznik = 0;
2, licznik = 1
4, licznik = 2
8, licznik = 3
6, licznik = 4
2, licznik = 5
4, licznik = 6
8, licznik = 7
6, licznik = 8
2, licznik = 9
4, licznik = 10
8, licznik = 11 - zwracamy 8

To mam i sprawdzając wartości z np. http://onlinemschool.com/math/formula/order_table/

Input:

2
12 8 
9 11 

12^8 = 429981696
9^11 = 31381059609
Output:

6
9

Wszystko się zgadza, lecz czas mnie nie puszcza i zastanawiam się co mógłbym zmienić.
Tutaj kod: (feedback mile widziany)

https://ideone.com/TA1xrb

public static int determine_value_at_position_of_an_array(List<int> arr, int potega)
/// skaczemy po naszej liście aż licznik (counter) będzie miał wartości potęga
/// i zwraca wartość z listy w tym miejscu.
/// a counter skacze po wartościach listy - od początku do końca i od nowa.

public static int get_last_number(int n)
/// zwraca ostatnią cyfrę liczby.

public static List<int> Pattern_Finder(int podstawa)
/// Tutaj znajdujemy nasz ciąg liczb który się powtarza cały czas im wyżej potęgujemy.
/// Ostatnia cyfra liczby podstawa to wartość otwierająca naszą sekwencję
/// Dalej po prostu potęgujemy naszą podstawę aż znajdziemy **drugi** początek(czyli wcześniejszy element był końcem), a w między 
/// czasie dodajemy te **ostatnie cyfry** do naszej listy.

public static int pow(int podstawa, int potega)
/// Po prostu podnosi liczbę podstawa do potęgi potega
/// Użyte do utworzenia sekwencji która będę przeszukiwał w determine_value_at_position_of_an_array.

public static int Answer_Finder(int podstawa, int potega) 
/// Sprawdzam podstawowe przypadki, wywołuje tworzenie sekwencji liczb
///  dla podanej podstawy, a określam ostatnią cyfrę liczby **podstawa** w potędze **potega** 
/// (czyli ostatnia czynność która jest wymagana do podania)

Z ciekawości, co to za dziwne błędy na ideone które i tak nie przeszkodziły wykonaniu się kodu?

Unhandled Exception:
System.NullReferenceException: Object reference not set to an instance of an object
  at Test+Program.Main () [0x00015] in <aadb5cd4cd0b40dfb6d217f3caa1c3e4>:0 
[ERROR] FATAL UNHANDLED EXCEPTION: System.NullReferenceException: Object reference not set to an instance of an object
  at Test+Program.Main () [0x00015] in <aadb5cd4cd0b40dfb6d217f3caa1c3e4>:0 
1

Jeśli lista ma powiedzmy 10 końcówek, to przecież wiesz od razu, że 22 potęga ma taką samą końcówkę jak 32 jak i 999592. Zaprzyjaźnij się z operacją modulo.

0

Nie trzeba sprawdzić wszystkich 10 możliwości ostatniej cyfry, ale tyle, ile jest kombinacji ostatniej cyfry (dopóki się nie powtórzy). Być może (np. dla 5) jest tylko jedna możliwość (5), więc pętla się wykona tylko raz. I nie używam pow(), bo to dla mięczaków :-).
Można wymyśleć coś szybszego? Bo mnie się nie udało...

    static int poteguj(int podst, int wyk)
    {
        int[] do_rozwazenia = new int[10];
        int pow = 1;
        for (int i = 0; i < 10; i++)
        {
            pow *= podst; // =aktualna potęga, od potęgi "2"                
            for (int j = 0; j < i; j++)                
                if (do_rozwazenia[j] == (pow % 10))            //tablica jest zapełniona, w 'i' jest ilość kombinacji ost. cyfry
                    return do_rozwazenia[(wyk - 1) % i];      //minus jeden, bo zaczelismy od 2 potęgi                                    
            do_rozwazenia[i] = pow % 10;
        }
        return -1; //brak rozwiązania ???
    }
0

To co ileś z pierwszego posta to za każdym razem, co drugi raz albo co 4 A co za tym idzie:

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

using namespace std;


int main()
{

    int ile;

    cin>>ile;

    for(int i=0;i<ile;i++)
    {
    long int p,w;
    cin >> p >> w;
    if (p > 10) p = p % 10;
    w = (w % 4) + 4;
    long int wynik = pow(p, w);
    cout << wynik % 10 << "\n";
    }

    return 0;
}
0
Jon Malevolt napisał(a):

Nie trzeba sprawdzić wszystkich 10 możliwości ostatniej cyfry, ale tyle, ile jest kombinacji ostatniej cyfry (dopóki się nie powtórzy). Być może (np. dla 5) jest tylko jedna możliwość (5), więc pętla się wykona tylko raz. I nie używam pow(), bo to dla mięczaków :-).
Można wymyśleć coś szybszego? Bo mnie się nie udało...

Exception jest na Splicie();
I to nie wina prędkości modulo, przecież główna pętla wykonuje się dla tych wejściowych parametrów max 4 razy//

https://ideone.com/X1wxZh

1 użytkowników online, w tym zalogowanych: 0, gości: 1