Given three numbers a, b, n. Find GCD(an, b).
Examples:
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
First Approach : Brute Force approach is to first compute a^n, then compute GCD of a^n and 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 codeint 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 codeif __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 bfunction 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> |
Output:
5
Time Complexity: O(n + log(min(a, b)), where n, a and b represents the given integer.
Auxiliary Space: O(log(min(a, b))), due to the recursive stack space.
But, what if n is very large (say > 10^9). Modular Exponentiation is the way. We know (a*b) % m = ( (a%m) * (b%m) ) % m). We also know gcd(a, b) = gcd(b%a, a) . So instead of computing ” pow(a, n), we use modular exponentiation.
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 bll powerGCD(ll a, ll b, ll n){ ll e = power(a, n, b); return gcd(e, b);}// Driver codeint 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 bdef powerGCD( a, b, n): e = power(a, n, b) return gcd(e, b) # Driver codeif __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> |
Output:
1
Time Complexity: O(logn + log(min(a, b)), where n, a and b represents the given integer.
Auxiliary Space: O(log(min(a, b))), due to the recursive stack space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
