Count pairs from an array having GCD equal to the minimum element in the pair | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int CountPairs ( int arr [ ] , int N ) { int res = 0 ; map < int , int > mp ; for ( int i = 0 ; i < N ; i ++ ) { mp [ arr [ i ] ] ++ ; } for ( auto p : mp ) { int x = p . first ; int y = p . second ; if ( x == 1 ) { res += N - 1 ; continue ; } res += ( y * ( y - 1 ) ) / 2 ; for ( int j = 2 ; j <= sqrt ( x ) ; j ++ ) { if ( x % j == 0 ) { res += mp [ j ] ; if ( j != x / j ) res += mp [ x / j ] ; } } } return res ; } int main ( ) { int arr [ ] = { 2 , 3 , 1 , 2 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << CountPairs ( arr , N ) ; return 0 ; }