Find the value of XXXX ... . . ( N times ) % M where N is large | Iterative function to calculate ( x ^ y ) % p in O ( log y ) ; Initialize result ; Update x if it is >= p ; If y is odd , multiply x with result ; y must be even now y = y 2 ; Function to return XXX ... . . ( N times ) % M ; Return the mod by M of smaller numbers ; Creating a string of N X 's ; Converting the string to int and calculating the modulo ; Checking the parity of N ; Dividing the number into equal half ; Utilizing the formula for even N ; Dividing the number into equal half ; Utilizing the formula for odd N ; Driver code ; Print XXX ... ( N times ) % M
< ? php function power ( $ x , $ y , $ p ) { $ res = 1 ; $ x = $ x % $ p ; while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ p ; $ y = $ y >> 1 ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } function findModuloByM ( $ X , $ N , $ M ) { if ( $ N < 6 ) { $ temp = chr ( 48 + $ X ) * $ N ; $ res = intval ( $ temp ) % $ M ; return $ res ; } if ( $ N % 2 == 0 ) { $ half = findModuloByM ( $ X , ( int ) ( $ N / 2 ) , $ M ) % $ M ; $ res = ( $ half * power ( 10 , ( int ) ( $ N / 2 ) , $ M ) + $ half ) % $ M ; return $ res ; } else { $ half = findModuloByM ( $ X , ( int ) ( $ N / 2 ) , $ M ) % $ M ; $ res = ( $ half * power ( 10 , ( int ) ( $ N / 2 ) + 1 , $ M ) + $ half * 10 + $ X ) % $ M ; return $ res ; } } $ X = 6 ; $ N = 14 ; $ M = 9 ; print ( findModuloByM ( $ X , $ N , $ M ) ) ; ? >