Compute power of power k times % 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
let N = 1000000 ; let phi = new Array ( N + 5 ) ; phi . fill ( 0 ) ; function computeTotient ( ) { for ( let i = 1 ; i <= N ; i ++ ) phi [ i ] = i ; for ( let p = 2 ; p <= N ; p ++ ) { if ( phi [ p ] == p ) { phi [ p ] = p - 1 ; for ( let i = 2 * p ; i <= N ; i += p ) { phi [ i ] = ( phi [ i ] / p ) * ( p - 1 ) ; } } } } function power ( x , y , p ) { while ( y > 0 ) { if ( ( y & 1 ) > 0 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } function calculate ( x , k , mod ) { let arr = new Array ( N ) ; arr . fill ( 0 ) ; let count = 0 ; while ( mod > 1 ) { arr [ count ++ ] = mod ; mod = phi [ mod ] ; } let result = 1 ; let loop = count + 1 ; arr [ count ] = 1 ; for ( let i = Math . min ( k , loop ) - 1 ; i >= 0 ; i -- ) result = power ( x , result , arr [ i ] ) ; return result ; } computeTotient ( ) ; let x = 3 , k = 2 , m = 3 ; document . write ( calculate ( x , k , m ) ) ;