Dados tres números x, y y p, calcule (x y ) % p.
Ejemplos:
Input: x = 2, y = 3, p = 5 Output: 3 Explanation: 2^3 % 5 = 8 % 5 = 3. Input: x = 2, y = 5, p = 13 Output: 6 Explanation: 2^5 % 13 = 32 % 13 = 6.
Hemos discutido soluciones recursivas e iterativas para el poder.
A continuación se discute la solución iterativa.
C++14
/* Iterative Function to calculate (x^y)%p in O(log y) */
#include <iostream>
using namespace std;
int power(int x, int y, int p)
{
// Initialize answer
int res = 1;
// Check till the number becomes zero
while (y > 0) {
// If y is odd, multiply x with result
if (y % 2 == 1)
res = (res * x);
// y = y/2
y = y >> 1;
// Change x to x^2
x = (x * x);
}
return res % p;
}
int main()
{
int x = 2;
int y = 5;
int p = 13;
cout << "Power is " << power(x, y, p);
return 0;
}
// This code is contributed by yaswanth0412
Java
/* Iterative Function to calculate (x^y)%p in O(log y) */
class GFG {
static int power(int x, int y, int p)
{
int res = 1; // Initialize result
while (y > 0) {
// If y is odd, multiply x with result
if ((y & 1) != 0)
res = res * x;
// y must be even now
y = y >> 1; // y = y/2
x = x * x; // Change x to x^2
}
return res % p;
}
public static void main(String[] args)
{
int x = 2;
int y = 5;
int p = 13;
int mod = power(x, y, p);
System.out.print("Power is " + mod);
}
}
// This code is contributed by Dharanendra L V.
Python3
# Iterative Function to calculate (x^y)%p in O(log y)
def power(x, y, p):
# Initialize result
res = 1
while (y > 0):
# If y is odd, multiply x with result
if ((y & 1) != 0):
res = res * x
# y must be even now
y = y >> 1 # y = y/2
x = x * x # Change x to x^2
return res % p
# Driver Code
x = 2
y = 5
p = 13
print("Power is ", power(x, y, p))
# This code is contributed by Khushboogoyal499
Javascript
<script>
/* Iterative Function to calculate (x^y) % p in O(log y) */
function power(x, y, p)
{
let res = 1; // Initialize result
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = res*x;
// y must be even now
y = y>>1; // y = y/2
x = x*x; // Change x to x^2
}
return res % p;
}
// Driver Code
let x = 2;
let y = 5;
let p = 13;
document.write("Power is " + power(x, y, p));
// This code is contributed by _saurabh_jaiswal
</script>
C#
/* Iterative Function to calculate (x^y)%p in O(log y) */
using System;
class GFG {
static int power(int x, int y, int p)
{
int res = 1; // Initialize result
while (y > 0) {
// If y is odd, multiply x with result
if ((y & 1) != 0)
res = res * x;
// y must be even now
y = y >> 1; // y = y/2
x = x * x; // Change x to x^2
}
return res % p;
}
// Driver Code
static public void Main()
{
int x = 2;
int y = 5;
int p = 13;
Console.Write("Power is " + power(x, y, p));
}
}
// This code is contributed by Dharanendra L V.
Producción
Power is 6
Complejidad de tiempo: O(log 2 y), donde y representa el valor de la entrada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Enfoque eficiente:
El problema con las soluciones anteriores es que puede ocurrir un desbordamiento para valores grandes de n o x. Por lo tanto, la potencia generalmente se evalúa bajo el módulo de un gran número.
A continuación se muestra la propiedad modular fundamental que se utiliza para calcular eficientemente la potencia bajo la aritmética modular.
(ab) mod p = ( (a mod p) (b mod p) ) mod p For example a = 50, b = 100, p = 13 50 mod 13 = 11 100 mod 13 = 9 (50 * 100) mod 13 = ( (50 mod 13) * (100 mod 13) ) mod 13 or (5000) mod 13 = ( 11 * 9 ) mod 13 or 8 = 8
A continuación se muestra la implementación basada en la propiedad anterior.
C++14
// Iterative C++ program to compute modular power
#include <iostream>
using namespace std;
/* Iterative Function to calculate (x^y)%p in O(log y) */
int power(long long x, unsigned int y, int p)
{
int res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
if (x == 0) return 0; // In case x is divisible by p;
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; // y = y/2
x = (x*x) % p;
}
return res;
}
// Driver code
int main()
{
int x = 2;
int y = 5;
int p = 13;
cout << "Power is " << power(x, y, p);
return 0;
}
// This code is contributed by shubhamsingh10
Java
// Iterative Java program to compute modular power
import java.io.*;
class GFG
{
/* Iterative Function to calculate (x^y) in O(log y) */
static int power(int x, int y, int p)
{
int res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
if (x == 0)
return 0; // In case x is divisible by p;
while (y > 0)
{
// If y is odd, multiply x with result
if ((y & 1) != 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Driver Code
public static void main(String[] args)
{
int x = 2;
int y = 5;
int p = 13;
System.out.print("Power is " + power(x, y, p));
}
}
// This code is contributed by Dharanendra L V.
Python3
# Iterative Python3 program
# to compute modular power
# Iterative Function to calculate
# (x^y)%p in O(log y)
def power(x, y, p) :
res = 1 # Initialize result
# Update x if it is more
# than or equal to p
x = x % 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 # y = y/2
x = (x * x) % p
return res
# Driver Code
x = 2; y = 5; p = 13
print("Power is ", power(x, y, p))
# This code is contributed by Nikita Tiwari.
C#
using System;
public class GFG
{
/* Iterative Function to calculate (x^y) in O(log y) */
static int power(int x, int y, int p)
{
int res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
if (x == 0)
return 0; // In case x is divisible by p;
while (y > 0)
{
// If y is odd, multiply x with result
if ((y & 1) != 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Driver Code
static public void Main ()
{
int x = 2;
int y = 5;
int p = 13;
Console.Write("Power is " + power(x, y, p));
}
}
// This code is contributed by Dharanendra L V.
PHP
<?php
// Iterative PHP program to
// compute modular power
// Iterative Function to
// calculate (x^y)%p in O(log y)
function power($x, $y, $p)
{
// Initialize result
$res = 1;
// Update x if it is more
// than or equal to p
$x = $x % $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/2
$y = $y >> 1;
$x = ($x * $x) % $p;
}
return $res;
}
// Driver Code
$x = 2;
$y = 5;
$p = 13;
echo "Power is ", power($x, $y, $p);
// This code is contributed by aj_36
?>
Javascript
// Iterative Javascript program to
// compute modular power
// Iterative Function to
// calculate (x^y)%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;
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/2
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Driver Code
let x = 2;
let y = 5;
let p = 13;
document.write("Power is " + power(x, y, p));
// This code is contributed by _saurabh_jaiswal
Producción
Power is 6
Complejidad de tiempo : O(Log y), donde y representa el valor de la entrada dada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Exponenciación modular (recursiva)
Este artículo es una contribución de Shivam Agrawal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA