Count of triplets in a given Array having GCD K | Python3 program to count the number of triplets in the array with GCD equal to K ; Frequency array ; mul [ i ] stores the count of multiples of i ; cnt [ i ] stores the count of triplets with gcd = i ; Return nC3 ; Function to count and return the number of triplets in the array with GCD equal to K ; Store frequency of array elements ; Store the multiples of i present in the array ; Count triplets with gcd equal to any multiple of i ; Remove all triplets which have gcd equal to a multiple of i ; Driver Code
MAXN = int ( 1e6 + 1 ) NEW_LINE freq = [ 0 ] * MAXN NEW_LINE mul = [ 0 ] * MAXN NEW_LINE cnt = [ 0 ] * MAXN NEW_LINE def nC3 ( n ) : NEW_LINE INDENT if ( n < 3 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return ( n * ( n - 1 ) * ( n - 2 ) ) / 6 NEW_LINE DEDENT def count_triplet ( arr , N , K ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT freq [ arr [ i ] ] += 1 NEW_LINE DEDENT for i in range ( 1 , 1000000 + 1 ) : NEW_LINE INDENT for j in range ( i , 1000000 + 1 , i ) : NEW_LINE INDENT mul [ i ] += freq [ j ] NEW_LINE DEDENT cnt [ i ] = nC3 ( mul [ i ] ) NEW_LINE DEDENT for i in range ( 1000000 , 0 , - 1 ) : NEW_LINE INDENT for j in range ( 2 * i , 1000000 + 1 , i ) : NEW_LINE INDENT cnt [ i ] -= cnt [ j ] NEW_LINE DEDENT DEDENT print ( " Number ▁ of ▁ triplets ▁ with ▁ GCD " " ▁ { 0 } ▁ are ▁ { 1 } " . format ( K , int ( cnt [ K ] ) ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 7 , 12 , 6 , 15 , 9 ] NEW_LINE N = 6 NEW_LINE K = 3 NEW_LINE count_triplet ( arr , N , K ) NEW_LINE DEDENT