Last Updated: 23 Apr, 2021

Cubic Square

Moderate

Asked in company

Solve now

Problem statement

You are given three positive integers ‘A’, ‘B’, and ‘M’. Your task is to find out the result of ‘A^B’ mod ‘M’.

This task was too easy for Ninja, and being a top-class ninja, he likes to make things a little difficult in order to enjoy solving them. So he converted B into base 3 and is now trying to find the answer.

But it seems like he made the task a little too difficult for himself. Being a good friend of Ninja, can you help find him ‘A^B mod M’ when ‘A’, ‘M’ is given in base 10 and ‘B’ is in base 3?

Input Format :

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.

The first line of each test case contains three positive integers, ‘A’, ‘B’, and ‘M’ respectively.

Output Format :

For each test case, print a single positive integer, the value of ‘A^B’ mod ‘M’.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= A <= 10^6
1 <= M <= 10^6
1 <= |B| <= 250

Where |B| is the number of digits of ‘B’ in base 3.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We know how to find a^b mod m if all are given in base 10.
One way of solving the problem is, therefore, to convert B back into base 10 and compute the answer.
But the length of B can be at max 250, therefore B < 3^251 which is a huge value and cannot be stored in an integer data type. Hence we need to do successive modular without computing the exact value of B.
We will do Exponentiation in this way:
- Take input B as a string, that way we do not need to worry about its magnitude.
- Let N be the length of B or as we can say the number of characters in the string B. Now, B[N-1] will be the least significant bit and B[0] will be the most significant bit.
- Keep a variable RESULT, which will store the answer. Initialize it with 1.
- Traverse B, for i goes from N - 1 to 0:
  - If B[i] == ‘1’ then multiply A to RESULT.
  - If B[i] == ‘2’ then multiply A, 2 times to RESULT.
  - In the end, A = A*A*A, because every increase in a bit’s position is symbolic of a rise by 3 in A’s power. Hence, indirectly we need to increase the magnitude of A three times.
- After every arithmetic operation, make sure to do %M.
At the end return the value of RESULT.

Solve now