Given three integers A, N and P, the task is to find (A^(N!)) % P.
Examples:
Input: A = 2, N = 1, P = 2
Output: 0
Explanation: As (2^(1!)) = 2
Therefore 2 % 2 will be 0.Input: A = 3, N = 3, P = 2
Output: 1
Naive Approach: The simplest solution of this problem can be find out factorial of N say f, and now calculate A to power f say pow and find its remainder with P.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to calculate factorial of a Number long long int fact( long long int n) { long long int ans = 1; // Calculating factorial for ( long long int i = 2; i <= n; i++) ans *= i; // Returning factorial return ans; } // Function to calculate resultant remainder long long int remainder( long long int n, long long int a, long long int p) { // Function call to calculate // factorial of n long long int len = fact(n); long long int ans = 1; // Calculating remainder for ( long long int i = 1; i <= len; i++) ans = (ans * a) % p; // Returning resultant remainder return ans; } // Driver Code int main() { // Given Input long long int A = 2, N = 1, P = 2; // Function Call cout << remainder(N, A, P) << endl; } |
Java
// Java program for the above approach import java.lang.*; import java.util.*; class GFG{ // Function to calculate factorial static int fact( int n) { int ans = 1 ; // Calculating factorial for ( int i = 2 ; i <= n; i++) ans *= i; // Returning factorial return ans; } // Function to calculate resultant remainder static int remainder( int n, int a, int p) { // Function call to calculate // factorial of n int len = fact(n); int ans = 1 ; // Calculating remainder for ( int i = 1 ; i <= len; i++) ans = (ans * a) % p; // Returning resultant remainder return ans; } // Driver Code public static void main(String args[]) { // Given Input int A = 2 , N = 1 , P = 2 ; // Function Call System.out.println(remainder(N, A, P)); } } // This code is contributed by sanjoy_62. |
Python3
# Python 3 program for above approach # Function to calculate factorial of a Number def fact(n): ans = 1 # Calculating factorial for i in range ( 2 ,n + 1 , 1 ): ans * = i # Returning factorial return ans # Function to calculate resultant remainder def remainder(n, a, p): # Function call to calculate # factorial of n len1 = fact(n) ans = 1 # Calculating remainder for i in range ( 1 ,len1 + 1 , 1 ): ans = (ans * a) % p # Returning resultant remainder return ans # Driver Code if __name__ = = '__main__' : # Given Input A = 2 N = 1 P = 2 # Function Call print (remainder(N, A, P)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; public class GFG{ // Function to calculate factorial static int fact( int n) { int ans = 1; // Calculating factorial for ( int i = 2; i <= n; i++) ans *= i; // Returning factorial return ans; } // Function to calculate resultant remainder static int remainder( int n, int a, int p) { // Function call to calculate // factorial of n int len = fact(n); int ans = 1; // Calculating remainder for ( int i = 1; i <= len; i++) ans = (ans * a) % p; // Returning resultant remainder return ans; } // Driver Code public static void Main( string []args) { // Given Input int A = 2, N = 1, P = 2; // Function Call Console.WriteLine(remainder(N, A, P)); } } // This code is contributed by AnkThon |
Javascript
<script> // Javascript program for above approach // Function to calculate factorial of a Number function fact(n) { let ans = 1; // Calculating factorial for (let i = 2; i <= n; i++) ans *= i; // Returning factorial return ans; } // Function to calculate resultant remainder function remainder(n, a, p) { // Function call to calculate // factorial of n let len = fact(n); let ans = 1; // Calculating remainder for (let i = 1; i <= len; i++) ans = (ans * a) % p; // Returning resultant remainder return ans; } // Driver Code // Given Input let A = 2, N = 1, P = 2; // Function Call document.write(remainder(N, A, P)); // This code is contributed by _saurabh_jaiswal. </script> |
0
Time complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: The above can be optimized using concept of modular exponentiation and some properties of modulo and powers:
- x^(a*b*c) can be written as :- (((x^a)^b)^c) …property of power.
- ((x^a)^b) % p can be written as :- ((x^a) %p)^b) % p …property of modulo.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to calculate // (A^N!)%P in O(log y) long long int power( long long x, long long int y, long long int p) { // Initialize result long long int res = 1; // Update x if it is more than or // Equal to p x = x % p; // In case 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) { // Initializing ans //to store final remainder long long int ans = a % p; // Calculating remainder for ( long long int i = 1; i <= n; i++) ans = power(ans, i, p); // Returning resultant remainder return ans; } // Driver Code int main() { // Given Input long long int A = 2, N = 1, P = 2; // Function Call cout << remainder(N, A, P) << endl; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { static long power( long x, long y, long p) { // Initialize result long res = 1 ; // Update x if it is more than or // Equal to p x = x % p; // In case x is divisible by p; if (x == 0 ) return 0 ; while (y > 0 ) { // If y is odd, // multiply x with result if ((y & 1 ) == 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 static long remainder( long n, long a, long p) { // Initializing ans to store final remainder long ans = a % p; // Calculating remainder for ( long i = 1 ; i <= n; i++) ans = power(ans, i, p); // Returning resultant remainder return ans; } // Driver Code public static void main(String[] args) { // Given Input long A = 2 , N = 1 , P = 2 ; // Function Call System.out.println(remainder(N, A, P)); } } // This code is contributed by maddler. |
Python3
# Python program for above approach # Function to calculate # (A^N!)%P in O(log y) def power(x, y, p): # Initialize result res = 1 # Update x if it is more than or # Equal to p x = x % p # In case 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 def remainder(n, a, p): # Initializing ans #to store final remainder ans = a % p # Calculating remainder for i in range ( 1 ,n + 1 ): ans = power(ans, i, p) # Returning resultant remainder return ans # Driver Code # Given Input A = 2 N = 1 P = 2 # Function Call print (remainder(N, A, P)) # This code is contributed by shivanisinghss2110 |
C#
/*package whatever //do not write package name here */ using System; class GFG { static long power( long x, long y, long p) { // Initialize result long res = 1; // Update x if it is more than or // Equal to p x = x % p; // In case x is divisible by p; if (x == 0) return 0; while (y > 0) { // If y is odd, // multiply x with result if ((y & 1) == 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 static long remainder( long n, long a, long p) { // Initializing ans to store final remainder long ans = a % p; // Calculating remainder for ( long i = 1; i <= n; i++) ans = power(ans, i, p); // Returning resultant remainder return ans; } // Driver Code public static void Main(String[] args) { // Given Input long A = 2, N = 1, P = 2; // Function Call Console.Write(remainder(N, A, P)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to calculate // (A^N!)%P in O(log y) function power(x, y, p) { // Initialize result let res = 1; // Update x if it is more than or // Equal to p x = x % p; // In case 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 function remainder(n, a, p) { // Initializing ans // to store final remainder let ans = a % p; // Calculating remainder for (let i = 1; i <= n; i++) ans = power(ans, i, p); // Returning resultant remainder return ans; } // Driver Code // Given Input let A = 2, N = 1, P = 2; // Function Call document.write(remainder(N, A, P) + "<br>" ); // This code is contributed by Potta Lokesh </script> |
0
Time complexity: O(N*logN)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!