Find First element in AP which is multiple of given prime | Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; Initialize result ; 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 find nearest element in common ; base conditions ; Driver code ; module both A and D ; function call
< ? php function power ( $ x , $ y , $ p ) { $ res = 1 ; $ x = $ x % $ p ; while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ p ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } function NearestElement ( $ A , $ D , $ P ) { if ( $ A == 0 ) return 0 ; else if ( $ D == 0 ) return -1 ; else { $ X = power ( $ D , $ P - 2 , $ P ) ; return ( $ X * ( $ P - $ A ) ) % $ P ; } } $ A = 4 ; $ D = 9 ; $ P = 11 ; $ A %= $ P ; $ D %= $ P ; echo NearestElement ( $ A , $ D , $ P ) ; ? >