Encuentra el resto cuando un número A elevado a N factorial se divide por P

Dados tres enteros A, N y P , la tarea es encontrar (A^(N!)) % P.

Ejemplos:

Entrada: A = 2, N = 1, P = 2
Salida: 0
Explicación: Como (2^(1!)) = 2 
Por lo tanto, 2 % 2 será 0.

Entrada: A = 3, N = 3, P = 2
Salida: 1

Enfoque ingenuo: la solución más simple de este problema puede ser encontrar el factorial de N , digamos f, y ahora calcule A para potenciar f, digamos pow , y encuentre su resto con P.

A continuación se muestra la implementación del enfoque anterior:

// 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 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.

# 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# 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

<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

Complejidad temporal: O(N!)
Espacio auxiliar: O(1)

Enfoque eficiente: lo anterior se puede optimizar utilizando el concepto de exponenciación modular y algunas propiedades de módulo y potencias:

1. x^(a*b*c) se puede escribir como :- (((x^a)^b)^c) …propiedad de la potencia. 
    
2. ((x^a)^b) % p se puede escribir como :- ((x^a) %p)^b) % p …propiedad del módulo.

A continuación se muestra la implementación del enfoque anterior:

// 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;
}

/*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.

# 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

/*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

<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

Complejidad temporal: O(N*logN)
Espacio auxiliar: O(1)