SPOJ LASTDIG

From Algorithmist
Jump to navigation Jump to search

3442 - The last digit[edit]

Summary[edit]

Nestor was doing the work of his math class about three days but he is tired of make operations a lot and he should deliver his task tomorrow. His math’s teacher gives two numbers a and b. The problem consist in find the last digit of the potency of base a and index b. Help Nestor with his problem. You are given two integer numbers: the base a (0 <= a <= 20) and the index b (0 <= b <= 2,147,483,000), a and b both are not 0. You have to find the last digit of a^b.

Explanation[edit]

This is a Modular exponentiation problem. It also has a high exponent.

The classic method of calculating exponentiation:

  1. Start your output number at 1.
  2. If the exponent is odd, multiply the output by the base, and subtract 1 from the exponent.
  3. Divide the exponent by 2, and multiply the base by itself.
  4. If the exponent is still greater than 0, loop back to step 2.

Since the result will never be greater than 10, you can apply modulus to the base and output at each step to keep the nubmers small.


Gotchas[edit]

  • Nothing special. If you followed the algorithm correctly and you get the stock input and output match, the program will be accepted.

Notes[edit]

  • Anything special to note about the problem.

Implementations[edit]

Notes/Hints on actual implementation here.

Optimizations[edit]

Optimizations here.

Input[edit]

2
3 10
6 2

Output[edit]

9
6

References[edit]

  1. Reference 1