Compute power of power k times % m | Python3 program to compute x ^ x ^ x ^ x . . % m ; Create an array to store phi or totient values ; Function to calculate Euler Totient values ; indicates not evaluated yet and initializes for product formula . ; Compute other Phi values ; If phi [ p ] is not computed already , then number p is prime ; Phi of a prime number p is always equal to p - 1. ; Update phi values of all multiples of p ; Add contribution of p to its multiple i by multiplying with ( 1 - 1 / p ) ; 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 ; Function to calculate ( x ^ x ^ x ^ x ... k times ) % m ; to store different mod values ; run loop in reverse to calculate result ; compute euler totient function values ; Calling function to compute answer
N = 1000000 NEW_LINE phi = [ 0 for i in range ( N + 5 ) ] NEW_LINE def computeTotient ( ) : NEW_LINE INDENT for i in range ( 1 , N + 1 ) : NEW_LINE INDENT phi [ i ] = i NEW_LINE DEDENT for p in range ( 2 , N + 1 ) : NEW_LINE INDENT if ( phi [ p ] == p ) : NEW_LINE INDENT phi [ p ] = p - 1 NEW_LINE for i in range ( 2 * p , N + 1 , p ) : NEW_LINE INDENT phi [ i ] = ( phi [ i ] // p ) * ( p - 1 ) NEW_LINE DEDENT DEDENT DEDENT DEDENT def power ( x , y , p ) : NEW_LINE INDENT while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % p NEW_LINE DEDENT x = ( x * x ) % p NEW_LINE DEDENT return res NEW_LINE DEDENT def calculate ( x , k , mod ) : NEW_LINE INDENT arr = [ 0 for i in range ( N ) ] NEW_LINE count = 0 NEW_LINE while ( mod > 1 ) : NEW_LINE INDENT arr [ count ] = mod NEW_LINE count += 1 NEW_LINE mod = phi [ mod ] NEW_LINE DEDENT result = 1 NEW_LINE loop = count + 1 NEW_LINE arr [ count ] = 1 NEW_LINE for i in range ( min ( k , loop ) , - 1 , - 1 ) : NEW_LINE INDENT result = power ( x , result , arr [ i ] ) NEW_LINE DEDENT return result NEW_LINE DEDENT computeTotient ( ) NEW_LINE x = 3 NEW_LINE k = 2 NEW_LINE m = 3 NEW_LINE print ( calculate ( x , k , m ) ) NEW_LINE