Efficiently Calculate the number of pairs in array satisfying the condition that gcd(a[i] , a[j]) > 1 and i!=j

Problem:

Given an array A of size N, count the number of pairs (i, j) where 1 ≤ i, j ≤ N, i ≠ j and gcd(A[i], A[j]) > 1.

Approach:

• Use the Inclusion-Exclusion Principle to efficiently compute the count of valid pairs.

• Instead of checking each pair individually (which is too slow), we count contributions of numbers with common factors.

• Use a frequency array to track occurrences of numbers in A.

• Use the Sieve of Eratosthenes to precompute prime numbers.

• Iterate over all possible numbers x and determine how many numbers in A are multiples of x.

• Factorize x and count the number of distinct prime factors to determine whether to add or subtract its contribution.

• Use combinatorics to efficiently count pairs using (cnt(x) * (cnt(x) — 1)) / 2.

Time Complexity: O(N log N + N K), where K is the maximum number of divisors any number in A can have.

Space Complexity: O(N log N).

How the Contribution is Calculated

To efficiently compute the number of valid pairs (i,j) such that gcd⁡(A[i],A[j])>1 , we use the Inclusion-Exclusion Principle (IEP). Let’s break it down.

Step 1: Counting Multiples of xxx

For each number x, we determine how many numbers in A are divisible by x. This is done efficiently using the frequency array (freq) and iterating over multiples of x.

• Let cnt(x) be the count of numbers in A that are multiples of x.
• If cnt(x) ≥ 2 , then we can form pairs where x is the GCD.

The number of ways to pick two elements from these cnt(x) numbers is:

cnt(x)×(cnt(x)−1)/2 ​

This is the standard formula for selecting 2 elements from a group of cnt(x) elements (i.e., nC2).

Step 2: Using Inclusion-Exclusion to Avoid Overcounting

Each number x contributes to the count, but since divisors of x also contribute, we must correctly add or subtract contributions to avoid overcounting.

Prime Factorization of x

To determine how to include x, we factorize x and count the number of distinct prime factors it has.

• If x has an odd number of distinct prime factors → Add its contribution.
• If x has an even number of distinct prime factors → Subtract its contribution.

This follows from the Inclusion-Exclusion Principle, where:

• Adding terms accounts for individual multiples.
• Subtracting terms removes duplicate contributions from divisors.

Example Calculation

Consider:

A=[2,3,4,6,9]

Step 1: Compute cnt(x) for different values of x

Step 2: Compute Prime Factorization

• 2 => { 2 } (number of factors is odd → Add)
• 3 => { 3 } (number of factors is odd → Add)
• 4 => { 2 } (number of factors is odd → Add, but cnt(4) = 1, so no effect)
• 6 => { 2, 3 } (number of factors is even → Subtract, but cnt(6) = 1, so no effect)
• 9 => {3 } ( number of factors is odd → Add, but cnt(9) = 1, so no effect)

Step 3: Compute Contributions

• For x =2 , cnt(2)=3 , so contribution (3×(3–1) )/2=3 → Add 3
• For x=3 , cnt(3)=3 so contribution (3×2)/2=3 → Add 3

Final Answer

Total Number of pairs is 3+3=6

Thus, the number of pairs where gcd⁡(A[i],A[j])>1 is 6.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
// Frequency array to store occurrences of each number in A
vector<int> freq(MAXN, 0); 
// List to store prime numbers
vector<int> primes; 
// Boolean array to mark prime numbers
bool is_prime[MAXN]; 

// Function to compute prime numbers up to n using Sieve of Eratosthenes
void sieve(int n) {
    fill(is_prime, is_prime + n + 1, true);
    is_prime[0] = is_prime[1] = false; 

    // 0 and 1 are not prime
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i); 

            // Store prime number
            for (int j = 2 * i; j <= n; j += i)
                is_prime[j] = false; 
        }
    }
}

// Function to count how many numbers in A are multiples of x
int countMultiples(int x, int n) {
    int count = 0;
    for (int multiple = x; multiple < MAXN; multiple += x) {
        count += freq[multiple];
    }
    return count;
}

int main() {
    int n;
    cin >> n;
    vector<int> A(n);

    // Read input and store frequency of each number in A
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        freq[A[i]]++;
    }

    // Precompute primes up to MAXN - 1
    sieve(MAXN - 1);

    long long result = 0;

    // Iterate over all possible values of x
    for (int x = 2; x < MAXN; x++) {
        int factors = 0, num = x;

        // Factorize x and count the number of distinct prime factors
        for (int p : primes) {
            if (p * p > num) break;
            if (num % p == 0) {
                factors++;
                while (num % p == 0) num /= p;
            }
        }

        // If num is still greater than 1, it's a prime factor itself
        if (num > 1) factors++; 

        // Count how many numbers in A are multiples of x
        int cnt = countMultiples(x, n);

        // Apply Inclusion-Exclusion Principle
        if (cnt > 1) {
            if (factors % 2 == 1)
                result += (1LL * cnt * (cnt - 1)) / 2; // Add contribution if odd number of prime factors
            else
                result -= (1LL * cnt * (cnt - 1)) / 2; // Subtract contribution if even number of prime factors
        }
    }

    // Output the final result
    cout << result << "\n";
    return 0;
}