SPOJ czy umiesz potęgować? Przekroczono limit czasu

Question

Cześć, mam problem. Otóż napisałem program ze spoja który powinien działać tak:

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

Napisałem swój program który u mnie działa bez zarzutów ale jak wklejam go do spoja dostaje informację, że przekroczono limit czasu. Proszę o pomoc!

Mój kod:

#include <iostream>
#include <math.h>
using namespace std;

int a,b,ile;
int  main()
{
cin>>ile;
for(int i=0; i<ile; i++)
{
cin>>a>>b;
int c=a;
if(b!=0){
for(int i=1; i<b; i++)
{
    a*=c;
}
cout<<(a%10)<<endl;
} else cout<<"1"<<endl;

}
return 0;
}

 

Comments

Zła kategoria

Answer 1

Nic dziwnego że przekroczyłeś limit czasu, bo stosujesz najprostsze rozwianie polegające właśnie na ... potęgowaniu. Tylko zauważ, że w tym zadaniu (1 ≤ a,b ≤ 1 000 000 000) - takie liczy nie zmieszczą się w zmiennej int, a ich potęgi to już w ogóle... (twój program wymięknie już przy 9^9 albo wcześniej).

Pierwszy problem to przechowywanie liczby - int nie pyknie, long long pewnie też nie starczy, pomyśl, jak sobie z tym poradzić, drugi problem to potęgowanie - na kij ci cała liczba jak potrzebujesz ostatniej cyfry - pomyśl, co ma pływ na ostatnią cyfrę a resztę która wpływu nie ma odrzuć.

Comments

Łatwo wyłapać cykl na tablicy potęg ;)