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.