Count of triplets in a given Array having GCD K | C ++ 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 Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAXN = 1e6 + 1 ; int freq [ MAXN ] = { 0 } ; int mul [ MAXN ] = { 0 } ; int cnt [ MAXN ] = { 0 } ; int nC3 ( int n ) { if ( n < 3 ) return 0 ; return ( n * ( n - 1 ) * ( n - 2 ) ) / 6 ; } void count_triplet ( vector < int > arr , int N , int K ) { for ( int i = 0 ; i < N ; i ++ ) { freq [ arr [ i ] ] ++ ; } for ( int i = 1 ; i <= 1000000 ; i ++ ) { for ( int j = i ; j <= 1000000 ; j += i ) { mul [ i ] += freq [ j ] ; } cnt [ i ] = nC3 ( mul [ i ] ) ; } for ( int i = 1000000 ; i >= 1 ; i -- ) { for ( int j = 2 * i ; j <= 1000000 ; j += i ) { cnt [ i ] -= cnt [ j ] ; } } cout << " Number ▁ of ▁ triplets ▁ " << " with ▁ GCD ▁ " << K ; cout << " ▁ are ▁ " << cnt [ K ] ; } int main ( ) { vector < int > arr = { 1 , 7 , 12 , 6 , 15 , 9 } ; int N = 6 , K = 3 ; count_triplet ( arr , N , K ) ; return 0 ; }