# SPOJ problem - The last digit of a number to a power

Here is the problem statement:

Given integers $a$ ($0 \le a \le 20$) and $b$ ($0 \le b \le 2,147,483,000$), where $a$ and $b$ are not both 0, find the last digit of $a^b$.

Input

The first line of input contains an integer $t$, the number of test cases ($t \le 30$). $t$ test cases follow. For each test case will appear $a$ and $b$ separated by a space.

Output

For each test case output an integer per line representing the result.

Example Input:

2
3 10
6 2

Example Output:

9
6

Here is the code which is exceeding the time limit:

#include <stdio.h>

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
long long int base,exponent;
scanf("%lld%lld",&base,&exponent);
if(base==0&&exponent==0)
{
printf("1\n");
}
else
{
long long int digit=1;
long long int i;
for(i=1;i<=exponent;i++)
{
digit=(base*digit)%10;
}
printf("%lld\n",digit);
}
}
return 0;
}

How do I make this more efficient?

As you have probably noticed, this is not efficient because you have a loop running exponent times (which could be over 2 billion). The way to make this more efficient is not to make your code faster, but to choose a better algorithm.

I'm not going to tell you outright what the answer is, but do the following. Add some output to your loop:

for(i=1;i<=exponent;i++)
{
digit=(base*digit)%10;
printf("digit = %d\n", digit);
}

and then run your program for some (small) sample inputs. You should notice a pattern. The key is to identify the pattern and use it to avoid running the loop a billion times.