A King's problem

When confronted with a problem similar to this, I find it very helpful to put the code aside at first and just focus on the mathematical aspects. I used knowledge of exponents in order to solve this problem. First, I determined which digits in integer number $A$ determined the last two digits of $A^B$ , or $A^B mod{100}$ . After a little bit of math, I determined that only the last two digits of number $A$ affected the last two digits of $A^B$ .

The idea behind this was that any integer number can be re-written as the sum of its components. For instance, $347$ can be rewritten as $300 + 47$ , and we know that $347^2$ is the same as $(300 + 47)^2$ . Since $300$ has two zeros as its last two digits, we know that multiplying it by any integer will result in a number whose last two digits are also zeros. This shows us that when raising $347$ to a power, any numbers before the $47$ are irrelevant when determining the last two digits of the result. This idea can be expanded and applied to any integer and any digit.

Now that I know this, I only need to work with the last to digits of $A$ to get my answer. But where do I go from here? The B value is still terribly large.

Through laws of exponents, we know that $A^B = A^C * A^ C$ for $C = B/2$ since $2C = B$ and $A^C * A^C = A^{C + C} + A^{2C}$ . If $B$ is odd, we can easily account for this by decreasing B by one to make it even and then accounting for this later by multiplying $A^C * A^C$ by $A$ (this adds one to the exponent.) We've now finished all of the mathematical aspects of this problem. Now we just have to put it into code.

Please ask any questions if any of my explanation is not clear, this is my first time writing an explanation. My program uses a recursive method to find the last two digits of $A^B$ . note: Make sure to include import java.util.*; at the top of your program.

public static int solveProblem(int A, int B)
{
    if(B == 0 || B == 1)
        return (int)Math.pow(A,B) % 100;

    //Figure out the last two digits.
    int lastTwoDigits = A % 100;
    int currentLastTwo = lastTwoDigits;

    int desiredPower = B;

    //If power is odd, temporarily make it even.
    if(desiredPower % 2 != 0)
        desiredPower--;

    //Recursively find the last two digits of A to half the desired power.
    int answer = solveProblem(lastTwoDigits, desiredPower / 2);

    //Raise the answer to the desired power.
    answer *= answer;

    //If the desired power was altered, account for this. 
    if(desiredPower == B - 1)
        answer *= lastTwoDigits;

    return answer % 100; 

}

public static void main(String[] args)
{
   long startTime = System.nanoTime();
   Scanner keyboard = new Scanner(System.in);

   int numberOfProblems = keyboard.nextInt();

   int sum = 0;

   for(int i = 1; i<= numberOfProblems; i++)
   {
       int a = keyboard.nextInt();
       int b = keyboard.nextInt();

       sum += solveProblem(a,b);
   }
   long endTime = System.nanoTime();

   System.out.println("Your sum is " + sum);
   System.out.println("Time to complete was " + ((endTime - startTime) / 1000000));

}