Count of quadruplets from range [ L , R ] having GCD equal to K | C ++ 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
#include <iostream> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } int countQuadruplets ( int l , int r , int k ) { int frequency [ r + 1 ] = { 0 } ; for ( int i = l ; i <= r ; i ++ ) { for ( int j = l ; j <= r ; j ++ ) { frequency [ gcd ( i , j ) ] ++ ; } } long 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 answer ; } int main ( ) { int l = 1 , r = 10 , k = 2 ; cout << countQuadruplets ( l , r , k ) ; return 0 ; }