Number of Quadruples with GCD equal to K | Java implementation of the approach ; 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
import java . util . * ; class GFG { static int nCr ( int n ) { if ( n < 4 ) return 0 ; int answer = n * ( n - 1 ) * ( n - 2 ) * ( n - 3 ) ; answer /= 24 ; return answer ; } static int countQuadruples ( int N , int K ) { int M = N / K ; int answer = nCr ( M ) ; for ( int i = 2 ; i < M ; i ++ ) { int j = i ; int temp2 = M / i ; int count = 0 ; int check = 0 ; int temp = j ; while ( j % 2 == 0 ) { count ++ ; j /= 2 ; if ( count >= 2 ) break ; } if ( count >= 2 ) { check = 1 ; } for ( int k = 3 ; k <= Math . sqrt ( temp ) ; k += 2 ) { int cnt = 0 ; while ( j % k == 0 ) { cnt ++ ; j /= k ; if ( cnt >= 2 ) break ; } if ( cnt >= 2 ) { check = 1 ; break ; } else if ( cnt == 1 ) count ++ ; } if ( j > 2 ) { count ++ ; } if ( check == 1 ) continue ; else { if ( count % 2 == 1 ) { answer -= nCr ( temp2 ) ; } else { answer += nCr ( temp2 ) ; } } } return answer ; } public static void main ( String [ ] args ) { int N = 10 , K = 2 ; System . out . println ( countQuadruples ( N , K ) ) ; } }