Find First element in AP which is multiple of given prime | Java Program to 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
class GFG { static int power ( int x , int y , int p ) { int res = 1 ; x = x % p ; while ( y > 0 ) { if ( ( y & 1 ) != 0 ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } static int NearestElement ( int A , int D , int P ) { if ( A == 0 ) return 0 ; else if ( D == 0 ) return - 1 ; else { int X = power ( D , P - 2 , P ) ; return ( X * ( P - A ) ) % P ; } } public static void main ( String args [ ] ) { int A = 4 , D = 9 , P = 11 ; A %= P ; D %= P ; System . out . println ( NearestElement ( A , D , P ) ) ; } }