Count pairs from an array having GCD equal to the minimum element in the pair | Python3 program for the above approach ; Function to count pairs from an array having GCD equal to minimum element of that pair ; Stores the resultant count ; Stores the frequency of each array element ; Traverse the array arr [ ] ; Iterate over the Map mp ; Stores the array element ; Stores the count of array element x ; If x is 1 ; Increment res by N - 1 ; Increment res by yC2 ; Iterate over the range [ 2 , sqrt ( x ) ] ; If x is divisible by j ; Increment the value of res by mp [ j ] ; If j is not equal to x / j ; Increment res by mp [ x / j ] ; Return the resultant count ; Driver Code
from math import sqrt NEW_LINE def CountPairs ( arr , N ) : NEW_LINE INDENT res = 0 NEW_LINE mp = { } NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( arr [ i ] in mp ) : NEW_LINE INDENT mp [ arr [ i ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT mp [ arr [ i ] ] = 1 NEW_LINE DEDENT DEDENT for key , value in mp . items ( ) : NEW_LINE INDENT x = key NEW_LINE y = value NEW_LINE if ( x == 1 ) : NEW_LINE INDENT res += N - 1 NEW_LINE continue NEW_LINE DEDENT res += ( y * ( y - 1 ) ) // 2 NEW_LINE for j in range ( 2 , int ( sqrt ( x ) ) + 1 , 1 ) : NEW_LINE INDENT if ( x % j == 0 ) : NEW_LINE INDENT res += mp [ j ] NEW_LINE if ( j != x // j ) : NEW_LINE INDENT res += mp [ x // j ] NEW_LINE DEDENT DEDENT DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 3 , 1 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE print ( CountPairs ( arr , N ) ) NEW_LINE DEDENT