Number of Quadruples with GCD equal to K | Function to calculate NC4 ; Base case to calculate NC4 ; Function to return the count of required quadruples using Inclusion Exclusion ; Effective N ; Iterate over 2 to M ; Number of divisors of i till M ; Count stores the number of prime divisors occurring exactly once ; To prevent repetition of prime divisors ; If repetition of prime divisors present ignore this number ; If prime divisor count is odd subtract it from answer else add ; Driver code
function nCr ( n ) { if ( n < 4 ) return 0 ; let answer = n * ( n - 1 ) * ( n - 2 ) * ( n - 3 ) ; answer = parseInt ( answer / 24 ) ; return answer ; } function countQuadruples ( N , K ) { let M = parseInt ( N / K ) ; let answer = nCr ( M ) ; for ( let i = 2 ; i < M ; i ++ ) { let j = i ; let temp2 = parseInt ( M / i ) ; let count = 0 ; let check = 0 ; let temp = j ; while ( j % 2 == 0 ) { count ++ ; j = parseInt ( j / 2 ) ; if ( count >= 2 ) break ; } if ( count >= 2 ) { check = 1 ; } for ( let k = 3 ; k <= Math . sqrt ( temp ) ; k += 2 ) { let cnt = 0 ; while ( j % k == 0 ) { cnt ++ ; j = parseInt ( j / k ) ; if ( cnt >= 2 ) break ; } if ( cnt >= 2 ) { check = 1 ; break ; } else if ( cnt == 1 ) count ++ ; } if ( j > 2 ) { count ++ ; } if ( check ) continue ; else { if ( count % 2 == 1 ) { answer -= nCr ( temp2 ) ; } else { answer += nCr ( temp2 ) ; } } } return answer ; } let N = 10 , K = 2 ; document . write ( countQuadruples ( N , K ) ) ;