Count of quadruplets from range [ L , R ] having GCD equal to K | Java implementation of the approach ; Function to return the gcd of a and b ; Function to return the count of quadruplets having gcd = k ; Count the frequency of every possible gcd value in the range ; To store the required count ; Calculate the answer using frequency values ; Return the required count ; Driver code
class GFG { static int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } static int countQuadruplets ( int l , int r , int k ) { int frequency [ ] = new int [ r + 1 ] ; for ( int i = l ; i <= r ; i ++ ) { for ( int j = l ; j <= r ; j ++ ) { frequency [ gcd ( i , j ) ] ++ ; } } long answer = 0 ; for ( int i = 1 ; i <= r ; i ++ ) { for ( int j = 1 ; j <= r ; j ++ ) { if ( gcd ( i , j ) == k ) { answer += ( frequency [ i ] * frequency [ j ] ) ; } } } return ( int ) answer ; } public static void main ( String args [ ] ) { int l = 1 , r = 10 , k = 2 ; System . out . println ( countQuadruplets ( l , r , k ) ) ; } }