Last number of exponentiation

Question

I have a little problem. The task was to accept input for variable d - which means number of tests, and output variables a and b. Every test is for another pair of a's and b's. The result of this code should be the last number of a^b exponentiation. Example:

//input
2 (it is d)
2 3 (a,b)
3 3 (a,b)

//output
8
7

This is how I tried to do that :

#include <iostream>
#include <cmath>

using namespace std;
int potega(int a, int b);

int main()
{   
int d;
int i;
cin >> d;
int t[d];
int a;
int b;
for(i=0; i<=d-1; i++)
{
    cin >> a >> b;
    t[i]=pow(a%10,b);
}
for(i=0; i<=d-1; i++)
{
    cout << t[i]%10 << endl;

 }
}

Do you have any suggestions? I'm a beginner. The execution time should be less than 0.529s.

Answer 1

Instead of looping through each of the powers you could use the decomposition of number into its square powers.

So if you have say the exponent of 7 it is exactly the same as (1 + 2 + 4) so you could use powers 1, 2 and 4 of the exponent this will speed up the exponent significantly. If you have exponent 9 (8 + 1) you square the number 3 times to get 8th power and you skip the powers 2 and 4 in multiplication.

So for any given two numbers you would store current a^(2^n) power of the number and than check if this particular power is in the binary representation of b.

This is also known as exponentiation by squaring and you can read more about it on this wiki site. Except in your modification you would actually always store the %10 rest of the number instead of the full number.