Optimised Approach
In order to optimise our code, we will recall our concept of exponents and powers.
 x^(a*b*c) = ((x^a)^b)^c
 (((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 rightshifted.
Space complexity: O(1).
FAQs

What is modular exponentiation?
Mostly used in publickey 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.

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.

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.