SPOJ, Czy umiesz potęgować ?, przekroczony czas programu C++

Question

Witam,

Mam problem z jednym zadaniem ze SPOJ, link do treści zadania - http://pl.spoj.com/problems/PA05_POT/.

Wydaje mi się, że program działa poprawnie lecz cały czas jest napisane, że przekroczono czas wykonania programu.

Tutaj mój kod:

#include <iostream>

using namespace std;

int main()
{

    int a,b;
    int wynik,ilosc;
    cin>>ilosc;
    for(int i=0;i<ilosc;i++)
    {
        wynik=1;
        cin>>a>>b;
        for(int j=0;j<b;j++)
        {
        wynik*=a;

        }
        wynik%=10;
        cout<<wynik<<endl;
    }

}

 

Answer 1

Zwróć uwagę, że w zadaniu jest napisane, że podstawa oraz wykładnik potęgi są większe lub równe jeden i mniejsze lub równe miliard. Jaki byłby czas działania twojego programu, gdybyś spróbował obliczyć wartość 1000000000¹⁰⁰⁰⁰⁰⁰⁰⁰⁰? Wykorzystaj to, że twoim zadaniem jest wypisanie tylko ostatniej cyfry danej potęgi, nie musisz obliczać całości. Podpowiedź: wypisz kolejne potęgi na kartce lub w excelu i postaraj się zauważyć powiązania między nimi.

Comments

Czy chodzi może o to, że np jak podstawa ma wykadnik 3 to  cały czas na końcu będą powtarzać się te same cyfry ? i tak samo dla wszystkich wykładników od 0-9 też zauważyłem w excelu, że odpowiednie cyfry jedności powtarzają się przy odpowiedniej reszcie z dzielania ale nie jestem pewien czy dobrze myślę.

---

Tak, jesteś na dobrej drodze.