Dados tres números a, b, n. Encuentre MCD(a n , b).
Ejemplos:
Input : a = 2, b = 3, n = 3 Output : 1 2^3 = 8. GCD of 8 and 3 is 1. Input : a = 2, b = 4, n = 5 Output : 4
Primer enfoque: el enfoque de fuerza bruta es calcular primero a ^ n, luego calcular GCD de a ^ n y b.
C++
// CPP program to find GCD of a^n and b.
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll gcd(ll a, ll b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Returns GCD of a^n and b.
ll powGCD(ll a, ll n, ll b)
{
for (int i = 0; i < n; i++)
a = a * a;
return gcd(a, b);
}
// Driver code
int main()
{
ll a = 10, b = 5, n = 2;
cout << powGCD(a, n, b);
return 0;
}
Java
// Java program to find GCD of a^n and b.
import java.io.*;
class GFG {
static long gcd(long a, long b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Returns GCD of a^n and b.
static long powGCD(long a, long n, long b)
{
for (int i = 0; i < n; i++)
a = a * a;
return gcd(a, b);
}
// Driver code
public static void main (String[] args) {
long a = 10, b = 5, n = 2;
System.out.println(powGCD(a, n, b));
}
}
// This code is contributed by anuj_67..
Python3
# Python 3 program to find # GCD of a^n and b. def gcd(a, b): if (a == 0): return b return gcd(b % a, a) # Returns GCD of a^n and b. def powGCD(a, n, b): for i in range(0, n + 1, 1): a = a * a return gcd(a, b) # Driver code if __name__ == '__main__': a = 10 b = 5 n = 2 print(powGCD(a, n, b)) # This code is contributed # by Surendra_Gangwar
C#
// C# program to find GCD of a^n and b.
using System;
class GFG
{
public static long gcd(long a, long b)
{
if (a == 0)
{
return b;
}
return gcd(b % a, a);
}
// Returns GCD of a^n and b.
public static long powGCD(long a,
long n, long b)
{
for (int i = 0; i < n; i++)
{
a = a * a;
}
return gcd(a, b);
}
// Driver code
public static void Main(string[] args)
{
long a = 10, b = 5, n = 2;
Console.WriteLine(powGCD(a, n, b));
}
}
// This code is contributed
// by Shrikant13
PHP
<?php
// PHP program to find GCD of a^n and b
function gcd($a, $b)
{
if ($a == 0)
return $b;
return gcd($b % $a, $a);
}
// Returns GCD of a^n and b.
function powGCD($a, $n, $b)
{
for ($i = 0; $i < $n; $i++)
$a = $a * $a;
return gcd($a, $b);
}
// Driver code
$a = 10;
$b = 5;
$n = 2;
echo powGCD($a, $n, $b);
// This code is contributed by ANKITRAI1
?>
Javascript
<script>
// javascript program to find GCD of a^n and b.
function gcd(a , b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Returns GCD of a^n and b.
function powGCD(a , n , b)
{
for (i = 0; i < n; i++)
a = a * a;
return gcd(a, b);
}
// Driver code
var a = 10, b = 5, n = 2;
document.write(powGCD(a, n, b));
// This code is contributed by gauravrajput1
</script>
Producción:
5
Complejidad de tiempo: O(n + log(min(a, b)), donde n, a y b representan el número entero dado.
Espacio auxiliar: O(log(min(a, b))), debido al espacio de pila recursivo .
Pero, ¿qué pasa si n es muy grande (digamos> 10^9). La exponenciación modular es el camino. Sabemos (a*b) % m = ( (a%m) * (b%m) ) % m). También sabemos mcd(a, b) = mcd(b%a, a) . Entonces, en lugar de calcular ” pow(a, n), usamos exponenciación modular .
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
/* Calculates modular exponentiation, i.e.,
(x^y)%p in O(log y) */
ll power(ll x, ll y, ll p)
{
ll res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to 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;
}
ll gcd(ll a, ll b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Returns GCD of a^n and b
ll powerGCD(ll a, ll b, ll n)
{
ll e = power(a, n, b);
return gcd(e, b);
}
// Driver code
int main()
{
ll a = 5, b = 4, n = 2;
cout << powerGCD(a, b, n);
return 0;
}
Java
// Java program of the above approach
import java.util.*;
class Solution{
/* Calculates modular exponentiation, i.e.,
(x^y)%p in O(log y) */
static long power(long x, long y, long p)
{
long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to 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;
}
static long gcd(long a, long b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Returns GCD of a^n and b
static long powerGCD(long a, long b, long n)
{
long e = power(a, n, b);
return gcd(e, b);
}
// Driver code
public static void main(String args[])
{
long a = 5, b = 4, n = 2;
System.out.print( powerGCD(a, b, n));
}
}
//contributed by Arnab Kundu
Python3
# Python3 program of the above approach # Calculates modular exponentiation, i.e., # (x^y)%p in O(log y) def power( x, y, p): res = 1 # Initialize result x = x % p # Update x if it is more than or # equal to 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 def gcd(a, b): if (a == 0): return b return gcd(b % a, a) # Returns GCD of a^n and b def powerGCD( a, b, n): e = power(a, n, b) return gcd(e, b) # Driver code if __name__ == "__main__": a = 5 b = 4 n = 2 print (powerGCD(a, b, n))
C#
// C# program of the above approach
using System;
class GFG
{
/* Calculates modular exponentiation,
i.e., (x^y)%p in O(log y) */
static long power(long x, long y, long p)
{
long res = 1; // Initialize result
x = x % p; // Update x if it is more
// than or equal to 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;
}
static long gcd(long a, long b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Returns GCD of a^n and b
static long powerGCD(long a, long b,
long n)
{
long e = power(a, n, b);
return gcd(e, b);
}
// Driver code
public static void Main()
{
long a = 5, b = 4, n = 2;
Console.Write( powerGCD(a, b, n));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP program of the above approach
// Calculates modular exponentiation,
// i.e.,(x^y)%p in O(log y)
function power($x, $y, $p)
{
$res = 1; // Initialize result
$x = $x % $p; // Update x if it is more
// than or equal to 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;
}
function gcd ($a, $b)
{
if ($a == 0)
return $b;
return gcd($b % $a, $a);
}
// Returns GCD of a^n and b
function powerGCD($a, $b, $n)
{
$e = power($a, $n, $b);
return gcd($e, $b);
}
// Driver code
$a = 5;
$b = 4;
$n = 2;
echo powerGCD($a, $b, $n);
// This code is contributed by Sachin.
?>
Javascript
<script>
// Javascript program of the above approach
/*
Calculates modular exponentiation,
i.e., (x^y)%p in O(log y)
*/
function power(x , y , p) {
var res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to 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;
}
function gcd(a , b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
// Returns GCD of a^n and b
function powerGCD(a , b , n) {
var e = power(a, n, b);
return gcd(e, b);
}
// Driver code
var a = 5, b = 4, n = 2;
document.write(powerGCD(a, b, n));
// This code contributed by Rajput-Ji
</script>
Producción:
1
Complejidad de tiempo: O(logn + log(min(a, b)), donde n, a y b representan el número entero dado.
Espacio auxiliar: O(log(min(a, b))), debido al espacio de pila recursivo .