Day 3 : Power Of Power

Easy
0/40
Average time to solve is 15m
profile
Contributed by
31 upvotes
Asked in company
HSBC

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 2 3 11
5 2 2 7
Sample Output 1 :
5
2
Explanation For Sample Output 1 :
For the first test case, the value of 2 ^ 3 is 8 and hence the value of 3 ^ 8 is 6561. 6561 mod 11 is 5. So the final Answer is 5.

For the second test case, the value of 2 ^ 2 is 4 and hence the value of 5 ^ 4 is 625. 625 mod 7 is 2. So the final Answer is 2.
Sample Input 2 :
2
3 9 4 19
55 69 21 998244353
Sample Output 2 :
18
441977229
Hint

Try Splitting B ^ C into t * (M-1) + y for using Fermat’s theorem on A ^ (B ^ C).

Approaches (1)
Fermat’s Theorem

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’.
Time Complexity

O(log( M ) + log( C )), Where M and C are the given numbers. 


Since We are calling the ‘powerModM’ Function twice, Once to compute B ^ C and second time to compute A ^ ‘res’ where ‘res’ can be ‘M’ in the worst case.

Space Complexity

O(1).

 

We don't have to create extra space, so the space complexity is O(1).

Code Solution
(100% EXP penalty)
Day 3 : Power Of Power
Full screen
Console