problem z kodem SPOJ

pytanie zadane 28 sierpnia 2016 w C i C++ przez pewien_programista Obywatel (1,070 p.)
zamknięte 28 sierpnia 2016 przez pewien_programista

Witam!

Mam problem, otóż internetowy sędzia kazał mi wypisać k razy (1 <= k <= 10) ostatnią liczbę potęgowania (1 <= a,b <= 1000000000). Program, który napisałem działa, ale z niewiadomych przyczyn sędzia nie chce go zaliczyć

#include <iostream>
#include <vector>

using namespace std;

int pow(int a, int b)
{
    if (b == 0) return 1;
    else if (b == 1) return a%10;
    else if (a%10 == 0) return 0;

    vector<int> last;
    bool found = false;
    last.push_back(0);

    unsigned long long int x = 1;
    int pattern = 0;
    for (int i=0; i<b; i++)
    {
        x*=a;
        int y = x%10;
        for (int j=0; j<last.size(); j++)
        {
            if (last[j] == y) found = true;
        }
        if (!found) last.push_back(y);
        if (found) break;
        pattern++;
    }
    unsigned long int mod;
    if (b%pattern == 0) mod = pattern;
    else mod = b%pattern;

    return last[mod];
}

int main()
{
    int x;
    cin >> x;
    int* a = new int[x];
    int* b = new int[x];
    for (int i=0; i<x; i++) cin >> a[i] >> b[i];
    for (int i=0; i<x; i++)cout << pow(a[i], b[i]) << endl;
    return 0;
}

Czego nie wziąłem pod uwagę?

komentarz zamknięcia: Dziękuję! Wiem już to co chciałem.

komentarz 28 sierpnia 2016 przez MetRiko Nałogowiec (37,110 p.)

Podaj link do zadania

komentarz 28 sierpnia 2016 przez pewien_programista Obywatel (1,070 p.)

http://pl.spoj.com/problems/PA05_POT/

2 odpowiedzi

odpowiedź 28 sierpnia 2016 przez Kasztan Dyskutant (8,080 p.)

odpowiedź 28 sierpnia 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Nie chce mi się czytać tego całego ale wiem, że taki zabieg pow(a[i], b[i]) nie będzie działał. Temat zresztą wałkowany na tym forum masę razy

komentarz 28 sierpnia 2016 przez pewien_programista Obywatel (1,070 p.)

Dlaczego? Z tego co wiem powinno działać. Przesyłam wartość i-tej szufladki tablicy do funkcji, tablica typu int, funkcja przyjmuje wartości typu int. Gdzie problem?

komentarz 28 sierpnia 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

No to źle wiesz:

1 funkcja pow liczy na doublach

2 mialiard do potęgi mialiarda = yyy??

Wystarczy czy mam wymieniać dalej ?

komentarz 28 sierpnia 2016 przez pewien_programista Obywatel (1,070 p.)

Zauważ, że nie jest to typowe potęgowanie, potęguje tylko do momentu, aż zacznie się powtarzać ostatnia liczba. np. dla 2^99999999 wykonuje tak naprawdę tylko 2^4 i zapisuje ostatnie cyfry wyników, które się powtarzają... a potem już modulo...

komentarz 28 sierpnia 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)
edycja 28 sierpnia 2016 przez ZakosiliMiNeta

To co robi np dla 999 999 999 albo 999 999 997? Do której potegi maksymalnie niby policzy? Przy okazji następna podpowiedź jaki wynik będzie dla 3^3 a jaki dla 33^3?

komentarz 28 sierpnia 2016 przez pewien_programista Obywatel (1,070 p.)

Nazwa funkcji pow może być myląca, gdyż ona nie potęguje (przynajmniej nie do tak dużej potęgi, jak jest podana), jeśli chodzi o pytanie dla 3^3 poda 7, podobnie jak dla 33^3 (kalkulator w telefonie mówi, że to wynik jaki chcę uzyskać) co to pierwszej części pytania (jak mniemam chodzi ci o potęgowanie 2) to ZAWSZE będzie kontynuował, do puki nie znajdzie powtarzających się liczb (kilka potęg 2: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096. Jak widzisz powtarza się sekwencja 2, 4, 8, 6, 2, 4, 8, 6... I to wykorzystuje mój program, dla innych liczb też działa np. dla 3 sekwencja to 3, 9, 7, 1). Kiedy takowe znajdzie, liczy która cyfra będzie ostatnia po podniesieniu do danej potęgi. Podsumowując: tak naprawdę nie liczę potęgi, ale jej ostatnią liczbę (bo tego wymaga zadanie). Zachęcam do zajrzenia do kodu.

komentarz 28 sierpnia 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Gościu wiem jak zrobić te zadanie. Dałem wystarczająco dużo wskazówek, wystarczy Ci tylko wykładnik, ostatnia cyfra podstawy i odpowiednie urzycie modulo. Dalej już powinieneś wpaść na prawidłowe rozwiązanie