Last Updated: 11 Dec, 2020

Day 3 : Power Of Power

Easy

Asked in company

Solve now

Problem statement

Hisoka was so hungry for power that he left Phantom Troupe in search of power. He met two kids on his way, Gon and Killua. They gave him four numbers A, B, C, and M where M is a Prime Number and told him that if he can calculate A ^ (B ^ C) Mod M, he will gain a lot of powers. Hisoka is weak in coding. Can you help hisoka solve this problem of powers.

For Example :

A = 2, B = 2, C = 3, M = 5

Computing B ^ C gives 2 ^ 3 = 8, Now A ^ (B ^ C) = 2 ^ 8 = 256.  256 Mod 5 is 1. Hence the final answer is 1.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then each test cases follow.

The first line of each test case contains four space-separated integers A, B, C, and M.

Output Format :

For each test case, print a single integer ‘ans’.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints :

1 <= T <= 100
1 <= A, B, C <= 10^9
1 < M <= 10^9 + 7


Time limit: 1 sec

Solve now

Approaches

01 Approach

According to Fermat’s theorem, A ^ (K - 1) = 1 (Mod K) if K is a Prime Number.

So we will try to convert A ^ (B ^ C) mod M to A ^ (t * (M - 1) + y) i.e. Convert B ^ C to

t * (M - 1) + y. By doing this, A ^ (t * (M - 1) + y) can be written as (A ^ (t * (M - 1)) * (A ^ (y)).

And according to Fermat's theorem, A ^ (t * (M - 1)) = 1 (Mod M).

So the final answer we have to compute is (A ^ y) Mod M, Where y is (B ^ C) Mod (M - 1).

The steps are as follows:

We will Make a function ‘powerModM’ which will help us to calculate A ^ B Mod M in log(B) time.
In the ‘powerModM’ function:
- Take a variable ‘pow’ to store the result.
- To compute (B ^ C) % M, Take a while loop till C>0:
  - If C is odd:
    - Update res = (res * B) % M.
  - Divide C by 2 and update B = (B * B) % M.
- Return ‘pow’.
In the Main function:
- Call the ‘powerModM’ function for B, C, M-1 and store the answer in a variable ‘res’.
- Call the ‘powerModM’ function again for A, res, M and store the answer in a variable ‘ans’.
- Return ‘ans’.

Solve now