Potęgowanie (zad. SPOJ) – przekraczanie limitu czasu

0

Witam! Jestem początkujący, więc z góry proszę o wyrozumiałość.
Robię jedno zadanie na SPOJ, bardzo proste, w którym chodzi o to, aby podnieść liczbę a do potęgi b. Można korzystać tylko z biblioteki iostream.
Zrobiłem je, ale niestety "przekraczam czas". Pomógłby ktoś i wyjaśnił jak to skrócić?

#include <iostream>

using namespace std;

int main()
{
    int x;
    cin>>x;
    int a[x-1], b[x-1];
    for (int i=0; i<x; i++)
    {
        cin>>a[i];
        cin>>b[i];
    }
    for (int i=0; i<x; i++)
    {
        int odp=a[i];
        if(b[i]==0)
        {
            odp=1;
            cout<<odp;
            cout<<endl;
        }
        else
        {

            for(int q=1; q<b[j]; q++)
            {
                odp=odp*a[j];
            }
            cout<<odp;
            cout<<endl;
        }
    }
    return 0;
}
0

Czy aby przypadkiem w tym zadaniu nie chodzi tylko o to, aby poznać ostatnią cyfrę tego działania?

Btw, na SPOJu wejście oraz wyjście są odrębnymi strumieniami - zatem nie musisz wczytywać danych do tablicy, możesz wypisywać wyniki od razu.

0

Daj linka do zadania

1

Jeśli chodzi o to zadanie http://pl.spoj.com/problems/PA05_POT/, to wypisz sobie kilka pierwszych potęgo dowolnej liczby, i przyjrzyj się ostatnim cyfrom. Bo właśnie o to chodzi w tym zadaniu, gdybyś chciał potęgować to wyniki znacznie przekroczyłyby nie tylko limit czasu ale i maksymalne wartości dostępnych w C++ zmiennych. Np wg mojego pythona 3 gdzie ma takich ograniczeń, 99 do potęgi 9999 ma 19955 cyfr, a przecież dane wejściowe mogą być dużo wyższe

0

To już było, wiele razy. Poszukaj.

0
  1. używasz VLA co jest rozszerzeniem od g++
  2. tablica jest za mała: a[x-1], więc masz Undefined Behavior. Najprawdopodobniej ostatni wpis w tablicy a nadpiszę ci wartość x.
  3. Jak wspomniano wyżej, tablice są niepotrzebne.
  4. Jak wspomniano wyżej, źle liczysz potęgę (algorytm najwolniejszy z możliwych i wykraczający poza zakres int).
0

Dzięki ;)
Temat do zamknięcia

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