human
Can you provide a code to find gcd ( a ^ n , c ) where a , n and c can vary from 1 to 10 ^ 9 and the other steps required given the following:
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"
Solution in Python:
assistant
#Here is code to find gcd ( a ^ n , c ) where a , n and c can vary from 1 to 10 ^ 9 and the other steps required.
 def modPower ( x , y , p ) :
	while ( y > 0 ) :
		if ( y & 1 ) :
			res = ( res * x ) % p
		x = ( x * x ) % p
	return res
def gcd ( a , b ) :
	if ( b == 0 ) :
		return a
	return gcd ( b , a % b )
def gcdPow ( a , n , c ) :
	if ( a % c == 0 ) :
		return c
	modexpo = modPower ( a , n , c )
	return gcd ( modexpo , c )
if __name__ == " _ _ main _ _ " :
	a = 10248585
	n = 1000000
	c = 12564
	print ( gcdPow ( a , n , c ) )