Compute power of power k times % m | Java program for computing 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 ; Driver Code ; compute euler totient function values ; Calling function to compute answer
class GFG { static int N = 1000000 ; static long phi [ ] = new long [ N + 5 ] ; static void computeTotient ( ) { for ( int i = 1 ; i <= N ; i ++ ) phi [ i ] = i ; for ( int p = 2 ; p <= N ; p ++ ) { if ( phi [ p ] == p ) { phi [ p ] = p - 1 ; for ( int i = 2 * p ; i <= N ; i += p ) { phi [ i ] = ( phi [ i ] / p ) * ( p - 1 ) ; } } } } 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 calculate ( long x , long k , long mod ) { long arr [ ] = new long [ N ] ; long count = 0 ; while ( mod > 1 ) { arr [ ( int ) count ++ ] = mod ; mod = phi [ ( int ) mod ] ; } long result = 1 ; long loop = count + 1 ; arr [ ( int ) count ] = 1 ; for ( int i = ( int ) Math . min ( k , loop ) - 1 ; i >= 0 ; i -- ) result = power ( x , result , arr [ i ] ) ; return result ; } public static void main ( String args [ ] ) { computeTotient ( ) ; long x = 3 , k = 2 , m = 3 ; System . out . println ( calculate ( x , k , m ) ) ; } }