Last Updated: 30 Jun, 2021

Modulo Calculation

Moderate

Asked in companies

Solve now

Problem statement

You are given four integers ‘A’, ‘B’, ‘C’, ‘M’ your task is to find ( ‘A’ ^ ‘B’ / ‘C’) % ‘M’.

Note: Greatest Common Divisor (gcd) of ‘C’ and ‘M’ will always be 1.

For Example:

For ‘A’ = 4, ‘B’ = 2, ‘C’ = 4, ‘M’ = 3,
‘A’ ^ ‘B’ / ‘C’ = 16 / 4, which is 4.
So, 4 % 3 is 1, hence the output will be 1.

Input Format:

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

The first line of each test case contains four space-separated integers ‘A’, ‘B’, ‘C’, ‘M’, representing the integers described in the problem statement.

Output Format:

For each test case, print an integer representing the task defined in the problem statement.

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.

Constraints:

1 <= T <= 10^4
1 <= A, B, C, M <= 10^9

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

Let’s break the task into simpler tasks. We can easily calculate (A ^ B) % M, but note that ( X / Y) % Z is not equal to ( ( X % Z ) / ( Y % Z ) ) % Z. We have to calculate modular multiplicative inverse for division operation. So we have to find an integer, say ‘INV’ such that ‘INV’ * C = 1 % M.

More details about modular multiplicative inverse can be found at the given link:

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Algorithm:

power function:
1. It will take A, B, and M as arguments and will return ( A ^ B ) % M.
2. Declare a variable ‘RES’ to store the result.
3. Iterate from 1 to B and at each iteration multiply ‘RES’ by A’ and take modulo M.
4. Finally, return the ‘RES’ variable.
modInverse function:
1. It will take C and M as arguments and will return ( C ^ -1) % M.
2. Declare a variable ‘RES’ to store the result.
3. Iterate from 1 to M and at each iteration check, if ( ( I % M) * ( C % M ) ) % M == 1 or not.
4. If the condition is true store I into res and break the loop.
5. Finally, return the ‘RES’ variable.
given function:
1. Calculate ( A ^ B ) % M and store it in the ‘ANS’ variable.
2. Now multiply ‘ANS’ by the modular multiplicative inverse of C with respect to M.
3. Finally, take the ‘ANS’ modulo M and return it.

Solve now

02 Approach

We will use modular exponentiation to calculate (A ^ B) % M in logarithmic time complexity. To calculate (C^ -1) % M, we will use the Extended Euclidean Algorithm.

The main idea of the algorithm is that two integers C and M can be represented as

C * X + M * Y = gcd(C, M), where X and Y are two integers. In this case, gcd(C, M) is 1.

More details about the Extended Euclidean Algorithm can be found at the given link:

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Algorithm:

power function:
1. It will take A, B, and M as arguments and will return ( A ^ B ) % M.
2. Declare a variable ‘RES’ to store the result.
3. Start a while loop till b becomes 0.
  1. If b is odd, multiply A to ‘ANS’ and take modulo M.
  2. Multiply A by A and take modulo M and reduce B to half.
4. Finally, return the ‘RES’ variable.
euclid function:
1. It is a recursive function that will take A, B, X, and Y as arguments and calculate X and Y.
2. If B is zero, set X to 1 and Y to 0.
3. Else call ‘euclid’ function with B, A % B, X, Y as parameters.
4. Now store the value of x to a variable called ‘TEMP’.
5. Store Y in X.
6. Store ‘TEMP’ - (A / B) * Y in Y.
modInverse function:
1. It will take C and M as arguments and will return ( C ^ -1) % M.
2. Declare two variables X and Y which are the parameters of the Extended Euclidean Algorithm.
3. Call the ‘euclid’ algorithm to calculate X.
4. Finally, return X by taking modulo M.
given function:
1. Calculate ( A ^ B ) % M and store it in the ‘ANS’ variable.
2. Now multiply ‘ANS’ by the modular multiplicative inverse of C with respect to M.
3. Finally, take the ‘ANS’ modulo M and return it.

Solve now