Find the remainder when a number A raised to N factorial is divided by P

Optimised Approach

In order to optimise our code, we will recall our concept of exponents and powers.

1. x^(a*b*c) = ((x^a)^b)^c
2. (((x^a)^b)^c)%p = (((((x^a)%p)^b)%p)^c)%p

The optimised approach to find the remainder when a number A raised to N factorial is divided by P is given below using modular exponentiation.

To calculate power, update x if x>=p by noting the remainder on dividing x by p. If x is divisible by p, return 0.

⬇

If y is odd, multiply the result with x and then note the remainder. Else right shift y by 1 bit(for division) and multiply x with x and note the remainder.

⬇

Output the result.

⬇

To calculate remainder, run a loop to calculate for powers calculated in each step.

⬇

Output the actual answer.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

try here

PseudoCode

Algorithm 

___________________________________________________________________

procedure power(long long x, long long int y, long long int p):

___________________________________________________________________

1.  res = 1

2.  x = x % p

3.  if x == 0: return 0

4. while (y > 0):

         if y & 1: res = (res * x) % p

         y = y >> 1

         x = (x * x) % p

    Return res.

end procedure

___________________________________________________________________

procedure remainder(long long int n, long long int a, long long int p):

___________________________________________________________________

1.  ans = a % p

2.  Run loop till n:

        ans = power(ans, i, p)

3.  Return ans

end procedure

Implementation in C++

// C++ program to find the remainder when a number A raised to N factorial is divided by P.
#include <bits/stdc++.h>
using namespace std;

long long int power(long long x, long long int y, long long int p)
{
	long long int res = 1;
	// Updating x
	x = x % p;

	// if x is divisible by p;
	if (x == 0)
		return 0;

	while (y > 0) {
	// If y is odd, multiply x with result
		if (y & 1)
		res = (res * x) % p;

		// y must be even now
		y = y >> 1;
		x = (x * x) % p;
	}
	// Returning modular power
	return res;
}


// Function to calculate resultant remainder
long long int remainder(long long int n, long long int a, long long int p)
{
	// storing final remainder
    long long int ans = a % p;

	// Calculating remainder
	for (long long int i = 1; i <= n; i++)
		ans = power(ans, i, p);
	// Return answer
	return ans;
}

int main()
{
	long long int A, N, P;
	cin>>A>>N>>P;

	// Function Call
	cout << remainder(N, A, P) << endl;
}

Output:

Sample Input: 
2
1
2
Sample Output:
0

Complexity Analysis

Time Complexity: O(N*log N).

Analysing Time Complexity:

All n elements are traversed once and then log n times because elements get right-shifted.

Space complexity: O(1).

FAQs

1. What is modular exponentiation?
   Mostly used in public-key cryptography, it is a method of exponentiation performed on modulus. Modular exponentiation is also referred to as power in modular arithmetic. It is mainly used to limit the given size of our integer coefficients in some kind of intermediate calculations and data.
    
2. List out the differences between modular arithmetic and ordinary arithmetic? 
   The result of modular arithmetic lies in the finite sets, whereas the result of ordinary arithmetic lies in infinite sets. This is because modular arithmetic involves calculating the remainders, which will be a finite integer.
    
3. What is the factorial of a number?
   It will return the product of all numbers less than the given number inclusive of the given number.

For example   
 4!=4*3*2*1=24.

Key Takeaways

This article taught us how to find the remainder when a number A raised to N factorial is divided by P by approaching the problem using the modular exponentiation concept. We discussed our problem's implementation using illustrations, pseudocode, and proper code.

We hope you could take away all critical and conceptual techniques like analysing problems by walking over the execution of the given examples and finding out the pattern followed.

Now, we recommend you practice problem sets based on number theory to master your fundamentals and enhance your learning. You can get a wide range and variety of questions similar to this on Coding Ninjas Studio. 

It's not the end. Must solve the problem of similar types. 

Happy Coding.