Count of all possible pairs having sum of LCM and GCD equal to N | Recursive function to return gcd of a and b ; Function to calculate and return LCM of two numbers ; Function to count pairs whose sum of GCD and LCM is equal to N ; Driver code
def __gcd ( a , b ) : NEW_LINE INDENT if b == 0 : NEW_LINE INDENT return a NEW_LINE DEDENT else : NEW_LINE INDENT return __gcd ( b , a % b ) NEW_LINE DEDENT DEDENT def lcm ( a , b ) : NEW_LINE INDENT return ( a * b ) // __gcd ( a , b ) NEW_LINE DEDENT def countPair ( N ) : NEW_LINE INDENT count = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT for j in range ( 1 , N + 1 ) : NEW_LINE INDENT if ( __gcd ( i , j ) + lcm ( i , j ) == N ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 14 NEW_LINE print ( countPair ( N ) ) NEW_LINE DEDENT