Exponenciación modular (recursiva)

Dados tres números a, b y c, necesitamos encontrar (a ^b ) % c
Ahora, ¿por qué «% c» después de la exponenciación, porque a ^b será realmente grande incluso para valores relativamente pequeños de a, b y eso es un problema ? porque el tipo de datos del lenguaje en el que tratamos de codificar el problema probablemente no nos permitirá almacenar un número tan grande.
Ejemplos: 
 

Input : a = 2312 b = 3434 c = 6789
Output : 6343

Input : a = -3 b = 5 c = 89 
Output : 24

Espacio Auxiliar: O(1)
 

La idea se basa en las siguientes propiedades.
Propiedad 1: 
(m * n) % p tiene una propiedad muy interesante: 
(m * n) % p =((m % p) * (n % p)) % p
Propiedad 2: 
si b es par: 
(a ^ b) % c = ((a ^ b/2) * (a ^ b/2))%c ? esto sugiere divide y vencerás 
si b es impar: 
(a ^ b) % c = (a * (a ^( b-1))%c
Propiedad 3: 
Si tenemos que devolver el mod de un número negativo x cuyo valor absoluto es menor que y: 
entonces (x + y) % y hará el truco
Nota: 
También como el producto de (a ^ b/2) * (a ^ b/2) y a * (a ^( b-1) puede causar desbordamiento, por lo tanto, debemos tener cuidado con esos escenarios 
 

// Recursive C++ program to compute modular power
#include <bits/stdc++.h>
using namespace std;
 
int exponentMod(int A, int B, int C)
{
    // Base cases
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;
 
    // If B is even
    long y;
    if (B % 2 == 0) {
        y = exponentMod(A, B / 2, C);
        y = (y * y) % C;
    }
 
    // If B is odd
    else {
        y = A % C;
        y = (y * exponentMod(A, B - 1, C) % C) % C;
    }
 
    return (int)((y + C) % C);
}
 
// Driver code
int main()
{
    int A = 2, B = 5, C = 13;
    cout << "Power is " << exponentMod(A, B, C);
    return 0;
}
 
// This code is contributed by SHUBHAMSINGH10

// Recursive C program to compute modular power
#include <stdio.h>
 
int exponentMod(int A, int B, int C)
{
    // Base cases
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;
 
    // If B is even
    long y;
    if (B % 2 == 0) {
        y = exponentMod(A, B / 2, C);
        y = (y * y) % C;
    }
 
    // If B is odd
    else {
        y = A % C;
        y = (y * exponentMod(A, B - 1, C) % C) % C;
    }
 
    return (int)((y + C) % C);
}
 
// Driver program to test above functions
int main()
{
   int A = 2, B = 5, C = 13;
   printf("Power is %d", exponentMod(A, B, C));
   return 0;
}

// Recursive Java program
// to compute modular power
import java.io.*;
 
class GFG
{
static int exponentMod(int A,
                       int B, int C)
{
         
    // Base cases
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;
     
    // If B is even
    long y;
    if (B % 2 == 0)
    {
        y = exponentMod(A, B / 2, C);
        y = (y * y) % C;
    }
     
    // If B is odd
    else
    {
        y = A % C;
        y = (y * exponentMod(A, B - 1,
                             C) % C) % C;
    }
     
    return (int)((y + C) % C);
}
 
// Driver Code
public static void main(String args[])
{
    int A = 2, B = 5, C = 13;
    System.out.println("Power is " +
                        exponentMod(A, B, C));
}
}
 
// This code is contributed
// by Swetank Modi.

# Recursive Python program
# to compute modular power
def exponentMod(A, B, C):
     
    # Base Cases
    if (A == 0):
        return 0
    if (B == 0):
        return 1
     
    # If B is Even
    y = 0
    if (B % 2 == 0):
        y = exponentMod(A, B / 2, C)
        y = (y * y) % C
     
    # If B is Odd
    else:
        y = A % C
        y = (y * exponentMod(A, B - 1,
                             C) % C) % C
    return ((y + C) % C)
 
# Driver Code
A = 2
B = 5
C = 13
print("Power is", exponentMod(A, B, C))
     
# This code is contributed
# by Swetank Modi.

// Recursive C# program
// to compute modular power
class GFG
{
static int exponentMod(int A, int B, int C)
{
         
    // Base cases
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;
     
    // If B is even
    long y;
    if (B % 2 == 0)
    {
        y = exponentMod(A, B / 2, C);
        y = (y * y) % C;
    }
     
    // If B is odd
    else
    {
        y = A % C;
        y = (y * exponentMod(A, B - 1,
                             C) % C) % C;
    }
     
    return (int)((y + C) % C);
}
 
// Driver Code
public static void Main()
{
    int A = 2, B = 5, C = 13;
    System.Console.WriteLine("Power is " +
                    exponentMod(A, B, C));
}
}
 
// This code is contributed
// by mits

<?php
// Recursive PHP program to
// compute modular power
function exponentMod($A, $B, $C)
{
    // Base cases
    if ($A == 0)
        return 0;
    if ($B == 0)
        return 1;
     
    // If B is even
    if ($B % 2 == 0)
    {
        $y = exponentMod($A, $B / 2, $C);
        $y = ($y * $y) % $C;
    }
     
    // If B is odd
    else
    {
        $y = $A % $C;
        $y = ($y * exponentMod($A, $B - 1,
                               $C) % $C) % $C;
    }
     
    return (($y + $C) % $C);
}
 
 
// Driver Code
$A = 2;
$B = 5;
$C = 13;
echo "Power is " . exponentMod($A, $B, $C);
 
// This code is contributed
// by Swetank Modi.
?>

<script>
 
// Recursive Javascript program
// to compute modular power
 
// Function to check if a given
// quadilateral is valid or not
function exponentMod(A, B, C)
{
     
    // Base cases
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;
     
    // If B is even
    var y;
    if (B % 2 == 0)
    {
        y = exponentMod(A, B / 2, C);
        y = (y * y) % C;
    }
     
    // If B is odd
    else
    {
        y = A % C;
        y = (y * exponentMod(A, B - 1,
                             C) % C) % C;
    }
     
    return parseInt(((y + C) % C));
}
 
// Driver code
var A = 2, B = 5, C = 13;
document.write("Power is " +
               exponentMod(A, B, C));
     
// This code is contributed by Khushboogoyal499
 
</script>

Power is 6

Complejidad de tiempo: O (logn)

Espacio auxiliar: O (logn)

Exponenciación modular iterativa.