KVNANT - Editorial

PROBLEM LINK:

Practice
Contest

Author: Varun Singh

DIFFICULTY:

EASY

PREREQUISITES:

Elementary Number Theory

PROBLEM:

Given two integers b and e, find the last digit of b^e.

QUICK EXPLANATION:

Every digit 0 through 9 has a pattern of 4 digits when raised to an exponential power. Store them in a 2D array, mod the exponent by 4 and look the result up in the 2D array for all queries in constant time.

EXPLANATION:

Each digit from 0 to 9 has a pattern of 4 digits when raised to an exponential power.

0 -> 0,0,0,0
1 -> 1,1,1,1
2 -> 2,4,8,6
3 -> 3,9,7,1
4 -> 4,6,4,6
5 -> 5,5,5,5
6 -> 6,6,6,6
7 -> 7,9,3,1
8 -> 8,4,2,6
9 -> 9,1,9,1

For example:
Last digit of 7^1 = 7
Last digit of 7^2 = 9
Last digit of 7^3 = 3
Last digit of 7^4 = 1 and the pattern will repeat again
Last digit of 7^5 = 7
Last digit of 7^6 = 9

So we mod the e by 4 and simply look up at the b row and e\%4 column.

Notice here 1$^{st}$ column corresponds to when e\%4 is 1, 2$^{nd}$ column corresponds to when e\%4 is 2, 3$^{rd}$ when e\%4 is 3 and 4$^{th}$ when e\%4 is 0.

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.