Find gcd ( a ^ n , c ) where a , n and c can vary from 1 to 10 ^ 9 | Iterative Function to calculate ( 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 ; Finds GCD of a and b ; Finds GCD of a ^ n and c ; check if c is a divisor of a ; First compute ( a ^ n ) % c ; Now simply return GCD of modulo power and c . ; Driver code
< ? php function modPower ( $ x , $ y , $ p ) { while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ p ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } function gcd ( $ a , $ b ) { if ( $ b == 0 ) return $ a ; return gcd ( $ b , $ a % $ b ) ; } function gcdPow ( $ a , $ n , $ c ) { if ( $ a % $ c == 0 ) return $ c ; $ modexpo = modPower ( $ a , $ n , $ c ) ; return gcd ( $ modexpo , $ c ) ; } $ a = 10248585 ; $ n = 1000000 ; $ c = 12564 ; echo gcdPow ( $ a , $ n , $ c ) ; ? >