Count of distinct GCDs among all the non | C ++ program for the above approach ; Function to calculate the number of distinct GCDs among all non - empty subsequences of an array ; variables to store the largest element in array and the required count ; Map to store whether a number is present in A ; calculate largest number in A and mapping A to Mp ; iterate over all possible values of GCD ; variable to check current GCD ; iterate over all multiples of i ; If j is present in A ; calculate gcd of all encountered multiples of i ; current GCD is possible ; return answer ; Driver code ; Input ; Function calling
#include <bits/stdc++.h> NEW_LINE using namespace std ; int distinctGCDs ( int arr [ ] , int N ) { int M = -1 , ans = 0 ; map < int , int > Mp ; for ( int i = 0 ; i < N ; i ++ ) { M = max ( M , arr [ i ] ) ; Mp [ arr [ i ] ] = 1 ; } for ( int i = 1 ; i <= M ; i ++ ) { int currGcd = 0 ; for ( int j = i ; j <= M ; j += i ) { if ( Mp [ j ] ) { currGcd = __gcd ( currGcd , j ) ; if ( currGcd == i ) { ans ++ ; break ; } } } } return ans ; } int main ( ) { int arr [ ] = { 3 , 11 , 14 , 6 , 12 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << distinctGCDs ( arr , N ) << endl ; return 0 ; }