GCD of a number raised to some power and another number | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; typedef long long int ll ; ll power ( ll x , ll y , ll p ) { while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } ll gcd ( ll a , ll b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } ll powerGCD ( ll a , ll b , ll n ) { ll e = power ( a , n , b ) ; return gcd ( e , b ) ; } int main ( ) { ll a = 5 , b = 4 , n = 2 ; cout << powerGCD ( a , b , n ) ; return 0 ; }