Find gcd(a^n, c) where a, n and c can vary from 1 to 10^9
Question problem states that find gcd() of two numbers out of which one number can be as big as (10^9)^(10^9) which cannot be stored in datatypes like long long int in C++
Examples:
Input : 1 1 1 Output : 1 Input : 10248585 1000000 12564 Output : 9
We know from Euclid’s algorithm that, gcd(a, b) = gcd(a % b, b). Now the problem remains to find a^n mod c. This could be done using modular exponentiation with O(logn) complexity.
C++
// CPP program to find GCD of a^n and b. #include <bits/stdc++.h> #define ll long long int using namespace std; /* Iterative Function to calculate (x^y)%p in O(log y) */ ll modPower(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; } // Finds GCD of a and b ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); } // Finds GCD of a^n and c ll gcdPow(ll a, ll n, ll c) { // check if c is a divisor of a if (a % c == 0) return c; // First compute (a^n) % c ll modexpo = modPower(a, n, c); // Now simply return GCD of modulo // power and c. return gcd(modexpo, c); } // Driver code int main() { ll a = 10248585, n = 1000000, c = 12564; cout << gcdPow(a, n, c); return 0; } |
Java
// Java program to find // GCD of a^n and b. class GFG { /* Iterative Function to calculate (x^y)%p in O(log y) */ static long modPower( 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; } // Finds GCD of a and b static long gcd( long a, long b) { if (b == 0 ) return a; return gcd(b, a % b); } // Finds GCD of a^n and c static long gcdPow( long a, long n, long c) { // check if c is a divisor of a if (a % c == 0 ) return c; // First compute (a^n) % c long modexpo = modPower(a, n, c); // Now simply return GCD // of modulo power and c. return gcd(modexpo, c); } // Driver code public static void main(String[] args) { long a = 10248585 , n = 1000000 , c = 12564 ; System.out.println(gcdPow(a, n, c)); } } // This code is contributed by mits |
Python 3
# Python3 program to find # GCD of a^n and b. # Iterative Function to # calculate (x^y)%p in O(log y) def modPower(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 # Finds GCD of a and b def gcd(a, b): if (b = = 0 ): return a return gcd(b, a % b) # Finds GCD of a^n and c def gcdPow(a, n, c): # check if c is a divisor of a if (a % c = = 0 ): return c # First compute (a^n) % c modexpo = modPower(a, n, c) # Now simply return GCD of # modulo power and c. return gcd(modexpo, c) # Driver code if __name__ = = "__main__" : a = 10248585 n = 1000000 c = 12564 print (gcdPow(a, n, c)) # This code is contributed # by ChitraNayal |
C#
// C# program to find // GCD of a^n and b. using System; class GFG { /* Iterative Function to calculate (x^y)%p in O(log y) */ static long modPower( 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; } // Finds GCD of a and b static long gcd( long a, long b) { if (b == 0) return a; return gcd(b, a % b); } // Finds GCD of a^n and c static long gcdPow( long a, long n, long c) { // check if c is a divisor of a if (a % c == 0) return c; // First compute (a^n) % c long modexpo = modPower(a, n, c); // Now simply return GCD // of modulo power and c. return gcd(modexpo, c); } // Driver code public static void Main() { long a = 10248585, n = 1000000, c = 12564; Console.Write(gcdPow(a, n, c)); } } // This code is contributed // by ChitraNayal |
PHP
<?php // PHP program to find GCD // of a^n and b. /* Iterative Function to calculate (x^y)%p in O(log y) */ function modPower( $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 ; } // Finds GCD of a and b function gcd( $a , $b ) { if ( $b == 0) return $a ; return gcd( $b , $a % $b ); } // Finds GCD of a^n and c function gcdPow( $a , $n , $c ) { // check if c is a divisor of a if ( $a % $c == 0) return $c ; // First compute (a^n) % c $modexpo = modPower( $a , $n , $c ); // Now simply return GCD // of modulo power and c. return gcd( $modexpo , $c ); } // Driver code $a = 10248585; $n = 1000000; $c = 12564; echo gcdPow( $a , $n , $c ); // This code is contributed // by Akanksha Rai(Abby_akku) ?> |
Javascript
<script> // Javascript program to find // GCD of a^n and b. /* Iterative Function to calculate (x^y)%p in O(log y) */ function modPower(x,y,p) { let 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; } // Finds GCD of a and b function gcd(a,b) { if (b == 0) return a; return gcd(b, a % b); } // Finds GCD of a^n and c function gcdPow(a,n,c) { // check if c is a divisor of a if (a % c == 0) return c; // First compute (a^n) % c let modexpo = modPower(a, n, c); // Now simply return GCD // of modulo power and c. return gcd(modexpo, c); } // Driver code let a = 10248585, n = 1000000, c = 12564; document.write(gcdPow(a, n, c)); // This code is contributed by rag2127 </script> |
Output:
9
Time Complexity: O(log(n)+log(c)).
Auxiliary Space : O(1)
Contact Us