Count of quadruplets from range [ L , R ] having GCD equal to K | 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
def gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a ; NEW_LINE DEDENT return gcd ( b , a % b ) ; NEW_LINE DEDENT def countQuadruplets ( l , r , k ) : NEW_LINE INDENT frequency = [ 0 ] * ( r + 1 ) ; NEW_LINE for i in range ( l , r + 1 ) : NEW_LINE INDENT for j in range ( l , r + 1 ) : NEW_LINE INDENT frequency [ gcd ( i , j ) ] += 1 ; NEW_LINE DEDENT DEDENT answer = 0 ; NEW_LINE for i in range ( l , r + 1 ) : NEW_LINE INDENT for j in range ( l , r + 1 ) : NEW_LINE INDENT if ( gcd ( i , j ) == k ) : NEW_LINE INDENT answer += ( frequency [ i ] * frequency [ j ] ) ; NEW_LINE DEDENT DEDENT DEDENT return answer ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT l , r , k = 1 , 10 , 2 ; NEW_LINE print ( countQuadruplets ( l , r , k ) ) ; NEW_LINE DEDENT