Counting Coprime Neighbors and Matching Bounds in Coprimality Graphs

Reducing four-index coprime search ('Sea, You & copriMe') to a 2-matching degree inequality in the coprimality graph and computing all vertex degrees via Möbius inversion.

The Problem: Disjoint Coprime Pairs

Consider the following algorithmic problem (from Codeforces “Sea, You & copriMe”): given an array of $n$ positive integers $a = (a_1, a_2, \dots, a_n)$ with $4 \le n \le 2 \cdot 10^5$ and $1 \le a_i \le m \le 10^6$, determine whether there exist four distinct indices $p, q, r, s \in {1, \dots, n}$ such that

$$\gcd(a_p, a_q) = 1 \qquad\text{and}\qquad \gcd(a_r, a_s) = 1.$$

Searching over quadruples takes $O(n^4)$ time, and even enumerating all pairs takes $O(n^2)$—both completely infeasible for $n = 2 \cdot 10^5$.

Instead of treating this as an ad-hoc case analysis over prime factors, we can solve the decision and counting core of the problem in two clean reductions:

  1. Graph-Theoretic Reduction: Formulate the existence of four distinct indices as a matching of size $2$ in the coprimality graph, and characterize valid first edges through a single degree inequality.
  2. Number-Theoretic Counting: Compute the exact degree $\deg(i)$ of every vertex in the coprimality graph in $O(m \log m + \sum \tau(a_i))$ time using Möbius inversion.

1. Reduction to a Degree Bound in the Coprimality Graph

Define the coprimality graph $G = (V, E)$ over the array indices:

  • $V = {1, 2, \dots, n}$;
  • $(i, j) \in E \iff i \ne j \text{ and } \gcd(a_i, a_j) = 1$.

Finding four distinct indices $(p, q, r, s)$ with $\gcd(a_p, a_q) = \gcd(a_r, a_s) = 1$ is equivalent to finding two vertex-disjoint edges $(u, v) \in E$ and $(r, s) \in E$ — that is, a matching of size $2$ in $G$.

For each vertex $i \in V$, let $\deg(i)$ denote the number of indices $j \ne i$ coprime to $a_i$, and let $K = |E|$ be the total number of edges in $G$:

$$\deg(i) = \bigl|{j \ne i : \gcd(a_i, a_j) = 1}\bigr|, \qquad K = |E| = \frac{1}{2}\sum_{i=1}^n \deg(i).$$

When Does Picking $(u, v)$ Leave Another Edge Behind?

Suppose we tentatively pick a coprime pair $(u, v) \in E$ as the first edge of our matching, and remove both endpoints $u$ and $v$ from $G$. Which edges are destroyed?

Every edge incident to $u$ or $v$ is removed. There are $\deg(u)$ edges incident to $u$ and $\deg(v)$ edges incident to $v$. Because $(u, v)$ itself is an edge in $E$, it is counted in both $\deg(u)$ and $\deg(v)$. By inclusion–exclusion, the exact number of deleted edges is:

$$|E_{\text{deleted}}| = \deg(u) + \deg(v) - 1.$$

Therefore, the residual graph $G \setminus {u, v}$ still contains at least one valid second edge $(r, s)$ if and only if:

$$K - \bigl(\deg(u) + \deg(v) - 1\bigr) \ge 1 \quad \Longleftrightarrow \quad \deg(u) + \deg(v) \le K.$$

Proposition (The 2-Matching Degree Criterion)

A matching of size $2$ exists in $G = (V, E)$ if and only if there exists an edge $(u, v) \in E$ such that:

$$\gcd(a_u, a_v) = 1 \qquad\text{and}\qquad \deg(u) + \deg(v) \le K.$$

Why Greedy Selection Fails: A Concrete Example

Consider the array $a = [4, 7, 9, 15]$. Let’s compute the coprime degrees:

  • $a_1 = 4$ is coprime with $7, 9, 15 \implies \deg(1) = 3$.
  • $a_2 = 7$ is coprime with $4, 9, 15 \implies \deg(2) = 3$.
  • $a_3 = 9$ is coprime with $4, 7 \implies \deg(3) = 2$ (since $\gcd(9, 15) = 3 > 1$).
  • $a_4 = 15$ is coprime with $4, 7 \implies \deg(4) = 2$.

The total number of edges in $G$ is $K = (3 + 3 + 2 + 2)/2 = 5$.

If we greedily pick the edge $(4, 7)$, we destroy $\deg(1) + \deg(2) - 1 = 3 + 3 - 1 = 5 = K$ edges ($\deg(1) + \deg(2) = 6 > K$), leaving only $(9, 15)$, which are not coprime! Conversely, the edge $(4, 9)$ satisfies $\deg(1) + \deg(3) = 3 + 2 = 5 \le K$, guaranteeing that the complementary pair $(7, 15)$ is coprime.


2. Computing All Vertex Degrees via Möbius Inversion

To apply the degree criterion $\deg(u) + \deg(v) \le K$, we first need to compute $\deg(1), \dots, \deg(n)$ and $K$ without checking all $\binom{n}{2}$ pairs.

For each integer $d \in [1, m]$, define the multiples count $C[d]$ as the number of elements in the array divisible by $d$:

$$C[d] = \bigl|{j \in {1, \dots, n} : d \mid a_j}\bigr| = \sum_{k \ge 1} \text{freq}[k \cdot d].$$

Using the fundamental Möbius identity $\sum_{d \mid g} \mu(d) = [g = 1]$, the number of array elements $a_j$ coprime to a fixed integer $x$ is:

$$\sum_{j=1}^n [\gcd(x, a_j) = 1] = \sum_{j=1}^n \sum_{d \mid \gcd(x, a_j)} \mu(d) = \sum_{d \mid x} \mu(d) \sum_{j : d \mid a_j} 1 = \sum_{d \mid x} \mu(d),C[d].$$

To obtain $\deg(i)$, we subtract the self-pair $j = i$, which contributes $1$ to the sum if and only if $\gcd(a_i, a_i) = a_i = 1$:

$$\deg(i) = \sum_{d \mid a_i} \mu(d),C[d] - [a_i = 1].$$


Self-Contained C++20 Degree Calculator

We can package the linear sieve, the $O(m \log m)$ harmonic multiples transform, and the Möbius degree evaluation into a clean C++20 class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

class CoprimeGraphAnalyzer {
public:
    explicit CoprimeGraphAnalyzer(int32_t max_val)
        : spf_(max_val + 1, 0), mu_(max_val + 1, 0) {
        mu_[1] = 1;
        for (int32_t i = 2; i <= max_val; ++i) {
            if (spf_[i] == 0) {
                spf_[i] = i;
                primes_.push_back(i);
                mu_[i] = -1;
            }
            for (const int32_t p : primes_) {
                if (p > spf_[i] || i * p > max_val) break;
                spf_[i * p] = p;
                if (p == spf_[i]) {
                    mu_[i * p] = 0;
                    break;
                }
                mu_[i * p] = -mu_[i];
            }
        }
    }

    // Generate all square-free divisors of x in O(2^omega(x))
    [[nodiscard]] std::vector<int32_t> squarefree_divisors(int32_t x) const {
        std::vector<int32_t> divs = {1};
        while (x > 1) {
            const int32_t p  = spf_[x];
            const size_t  sz = divs.size();
            for (size_t i = 0; i < sz; ++i) {
                divs.push_back(divs[i] * p);
            }
            while (x % p == 0) x /= p;
        }
        return divs;
    }

    // Compute all vertex degrees deg[i] and total edge count K in O(m log m + n * 2^omega)
    [[nodiscard]] std::pair<std::vector<int32_t>, int64_t>
    compute_degrees(const std::vector<int32_t>& a) const {
        const int32_t n       = static_cast<int32_t>(a.size());
        const int32_t max_val = *std::ranges::max_element(a);

        std::vector<int32_t> freq(max_val + 1, 0);
        for (const int32_t x : a) ++freq[x];

        // Harmonic divisor transform: C[d] = number of elements divisible by d
        std::vector<int32_t> mult_cnt(max_val + 1, 0);
        for (int32_t d = 1; d <= max_val; ++d) {
            for (int32_t mult = d; mult <= max_val; mult += d) {
                mult_cnt[d] += freq[mult];
            }
        }

        std::vector<int32_t> deg(n, 0);
        int64_t sum_degrees = 0;

        for (int32_t i = 0; i < n; ++i) {
            int32_t d = 0;
            for (const int32_t div : squarefree_divisors(a[i])) {
                d += mu_[div] * mult_cnt[div];
            }
            if (a[i] == 1) --d; // Exclude self-loop when gcd(1, 1) == 1
            deg[i]       = d;
            sum_degrees += d;
        }

        return {deg, sum_degrees / 2};
    }

private:
    std::vector<int32_t> primes_;
    std::vector<int32_t> spf_;
    std::vector<int32_t> mu_;
};

int main() {
    const CoprimeGraphAnalyzer analyzer(1'000'000);
    const std::vector<int32_t> a = {4, 7, 9, 15};

    const auto [deg, total_edges] = analyzer.compute_degrees(a);
    std::cout << "Total coprime edges K = " << total_edges << "\n";
    for (size_t i = 0; i < a.size(); ++i) {
        std::cout << "a[" << i << "] = " << a[i] << " -> deg = " << deg[i] << "\n";
    }
    return 0;
}

Complexity of the Reduction

  • Harmonic Multiples Transform: $\sum_{d=1}^m \lfloor m/d \rfloor = O(m \log m)$ additions.
  • Square-Free Divisor Evaluation: At most $2^{\omega(a_i)} \le 128$ operations per element for $a_i \le 10^6$.

Having computed $\deg(i)$ for every vertex and $K = |E|$ in near-linear time, the entire four-index problem reduces to finding a single coprime pair $(u, v)$ satisfying $\deg(u) + \deg(v) \le K$.