GCD of a number raised to some power and another number | Java program of the above approach ; Calculates modular exponentiation , i . e . , ( x ^ y ) % p in O ( log y ) ; x = x % p ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1 ; y = y / 2 ; Returns GCD of a ^ n and b ; Driver code
import java . util . * ; class Solution { static long power ( long x , long y , long p ) { while ( y > 0 ) { if ( ( y & 1 ) != 0 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } static long gcd ( long a , long b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } static long powerGCD ( long a , long b , long n ) { long e = power ( a , n , b ) ; return gcd ( e , b ) ; } public static void main ( String args [ ] ) { long a = 5 , b = 4 , n = 2 ; System . out . print ( powerGCD ( a , b , n ) ) ; } }