Monotonic Sliding Windows over Sorted Degrees: Finding Disjoint Coprime Pairs

Finding a degree-bounded coprime edge in O(N log N) time using a monotonic sliding window with dynamic Möbius counts, reconstructing the disjoint pair, and proving completeness.

Searching for a Degree-Bounded Edge Without Quadratic Enumeration

Suppose we are given an integer array $a = (a_1, \dots, a_n)$ and its coprimality graph $G = (V, E)$, where $(u, v) \in E \iff \gcd(a_u, a_v) = 1$, every vertex degree $\deg(i)$ is known, and the total number of edges is $K = |E|$.

As established by inclusion–exclusion on $G$, two vertex-disjoint edges (a matching of size $2$, corresponding to four distinct indices with $\gcd(a_p, a_q) = \gcd(a_r, a_s) = 1$) exist in $G$ if and only if there is at least one edge $(u, v) \in E$ satisfying the degree sum bound:

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

Once such a first edge $(u, v)$ is identified, removing $u$ and $v$ destroys $\deg(u) + \deg(v) - 1 < K$ edges, guaranteeing that at least one disjoint edge $(r, s)$ survives in $G \setminus {u, v}$.

The algorithmic challenge is clear: there can be $\Theta(n^2)$ pairs $(u, v)$ satisfying $\deg(u) + \deg(v) \le K$, and we cannot afford to test their GCDs one by one. How do we find a coprime pair among them in near-linear time?


1. Monotonicity of the Degree-Admissible Window

Let $p_0, p_1, \dots, p_{n-1}$ be the permutation of vertex indices sorted in non-decreasing order of their degrees:

$$\deg(p_0) \le \deg(p_1) \le \dots \le \deg(p_{n-1}).$$

By symmetry between $u$ and $v$, we can assume $u = p_i$ and $v = p_j$ with $i < j$. For each position $i$, define the right boundary $R(i)$ of admissible partners:

$$R(i) = \max\bigl{j > i : \deg(p_j) \le K - \deg(p_i)\bigr},$$

with $R(i) = i$ if the set is empty. Every valid partner $p_j$ ($j > i$) for $p_i$ must lie inside the contiguous index window:

$$A_i = {p_{i+1}, p_{i+2}, \dots, p_{R(i)}}.$$

The Structural Key: $A_i$ Only Shrinks

As $i$ advances from $0$ to $n - 1$:

  • The left endpoint $i + 1$ strictly increases.
  • Because $\deg(p_i)$ is non-decreasing, the upper budget $K - \deg(p_i)$ is non-increasing, which implies $R(i+1) \le R(i)$.
1
2
3
4
Sorted indices:   p_0   p_1   p_2   p_3   p_4   p_5   p_6   p_7
Window A_0 (i=0):       [─────────────────────────────] R(0)=6
Window A_1 (i=1):             [─────────────────]       R(1)=5
Window A_2 (i=2):                   [─────]             R(2)=3

Because the left endpoint only moves right and the right endpoint only moves left, no vertex ever enters $A_i$ after $i = 0$. Every vertex enters $A_0$ at most once during initialization and is removed from the active window at most once across the entire loop!


2. Dynamic Möbius Counting on the Sliding Window

To test whether the active window $A_i$ contains at least one element coprime to $a_{p_i}$ without scanning $A_i$, we maintain the dynamic divisor frequency table over $A_i$:

$$M_i[d] = \bigl|{x \in A_i : d \mid a_x}\bigr|.$$

Whenever an index $x$ enters or leaves the window (delta = +1 or -1), we update $M_i[d]$ for all square-free divisors $d \mid a_x$ in $O(2^{\omega(a_x)})$ time. Then, by Möbius inversion restricted to $A_i$, the exact number of elements in $A_i$ coprime to $a_{p_i}$ is:

$$\text{coprime_in_window}(p_i, A_i) = \sum_{d \mid a_{p_i}} \mu(d),M_i[d].$$

Count Many Times, Scan at Most Once

For each $i = 0, \dots, n - 1$:

  1. Evaluate $\sum_{d \mid a_{p_i}} \mu(d),M_i[d]$ in $O(2^{\omega(a_{p_i})})$ operations.
  2. If the count is $0$: No valid partner for $p_i$ exists in $A_i$. Shrink the window from $A_i$ to $A_{i+1}$ and continue.
  3. If the count is $> 0$: A coprime partner is guaranteed to exist inside $A_i$! We linearly scan $j \in [i + 1, R(i)]$ until we find the first $p_j$ with $\gcd(a_{p_i}, a_{p_j}) = 1$, lock in $(u, v) = (p_i, p_j)$ as our first edge, and break immediately.

Because the linear gcd scan executes at most once (on the very first $i$ where the Möbius count is positive), its total cost across the entire algorithm is $O(n)$.


3. Reconstructing the Second Disjoint Edge

Once the first edge $(u, v)$ is found, we decrement the divisors of $a_u$ and $a_v$ from the global divisor table $C[d]$ to obtain the residual table $C_{\text{rem}}[d]$ on $V \setminus {u, v}$.

For each remaining vertex $r \notin {u, v}$, we evaluate its residual degree:

$$\deg_{\text{rem}}(r) = \sum_{d \mid a_r} \mu(d),C_{\text{rem}}[d] - [a_r = 1].$$

Since $\deg(u) + \deg(v) \le K$, at least one $r \notin {u, v}$ has $\deg_{\text{rem}}(r) > 0$. The moment we encounter the first such $r$, a single $O(n)$ scan over $s \notin {u, v, r}$ locates a partner with $\gcd(a_r, a_s) = 1$, completing the quadruple $(u, v, r, s)$.


Complete C++20 Implementation

Below is the self-contained C++20 solver implementing the monotonic sliding window and residual reconstruction:

  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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <optional>
#include <vector>

struct Quadruple {
    int32_t u, v, r, s; // 1-based indices
};

class CoprimeQuadrupleSolver {
public:
    explicit CoprimeQuadrupleSolver(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];
            }
        }
    }

    [[nodiscard]] std::optional<Quadruple> solve(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];

        std::vector<int32_t> mult_cnt(max_val + 1, 0);
        for (int32_t d = 1; d <= max_val; ++d) {
            for (int32_t m = d; m <= max_val; m += d) {
                mult_cnt[d] += freq[m];
            }
        }

        // Precompute square-free divisors and vertex degrees
        std::vector<std::vector<int32_t>> divs(n);
        std::vector<int64_t> deg(n, 0);
        int64_t total_deg = 0;

        for (int32_t i = 0; i < n; ++i) {
            divs[i] = squarefree_divisors(a[i]);
            int64_t d = 0;
            for (const int32_t div : divs[i]) {
                d += static_cast<int64_t>(mu_[div]) * mult_cnt[div];
            }
            if (a[i] == 1) --d;
            deg[i]     = d;
            total_deg += d;
        }

        const int64_t total_edges = total_deg / 2;
        if (total_edges == 0) return std::nullopt;

        // Sort vertex indices by non-decreasing degree
        std::vector<int32_t> order(n);
        std::iota(order.begin(), order.end(), 0);
        std::ranges::sort(order, [&](int32_t lhs, int32_t rhs) {
            return deg[lhs] < deg[rhs];
        });

        // Compute monotonic right bounds R(i) via two-pointer scan
        std::vector<int32_t> reach(n, 0);
        for (int32_t i = 0, r = n - 1; i < n; ++i) {
            while (r > i && deg[order[i]] + deg[order[r]] > total_edges) {
                --r;
            }
            reach[i] = std::max(i, r);
        }

        // Initialize active window A_0 = {order[1], ..., order[reach[0]]}
        std::vector<int32_t> active_mult(max_val + 1, 0);
        auto update_window = [&](int32_t pos, int32_t delta) {
            for (const int32_t div : divs[order[pos]]) {
                active_mult[div] += delta;
            }
        };

        int32_t win_l = 1;
        int32_t win_r = reach[0];
        for (int32_t pos = win_l; pos <= win_r; ++pos) {
            update_window(pos, +1);
        }

        int32_t first_u = -1;
        int32_t first_v = -1;

        for (int32_t i = 0; i < n; ++i) {
            if (win_l <= win_r) {
                const int32_t u = order[i];
                int32_t coprime_cnt = 0;
                for (const int32_t div : divs[u]) {
                    coprime_cnt += mu_[div] * active_mult[div];
                }

                if (coprime_cnt > 0) {
                    for (int32_t pos = win_l; pos <= win_r; ++pos) {
                        const int32_t v = order[pos];
                        if (std::gcd(a[u], a[v]) == 1) {
                            first_u = u;
                            first_v = v;
                            break;
                        }
                    }
                    break;
                }
            }

            if (i + 1 >= n) break;
            const int32_t next_l = i + 2;
            const int32_t next_r = reach[i + 1];

            while (win_r > next_r && win_r >= win_l) update_window(win_r--, -1);
            while (win_l < next_l && win_l <= win_r) update_window(win_l++, -1);
            win_l = next_l;
            win_r = std::max(next_l - 1, next_r);
        }

        if (first_u == -1) return std::nullopt;

        // Reconstruct the second disjoint edge in G \ {first_u, first_v}
        for (const int32_t div : divs[first_u]) --mult_cnt[div];
        for (const int32_t div : divs[first_v]) --mult_cnt[div];

        for (int32_t r = 0; r < n; ++r) {
            if (r == first_u || r == first_v) continue;

            int32_t rem_deg = 0;
            for (const int32_t div : divs[r]) {
                rem_deg += mu_[div] * mult_cnt[div];
            }
            if (a[r] == 1) --rem_deg;

            if (rem_deg > 0) {
                for (int32_t s = 0; s < n; ++s) {
                    if (s == first_u || s == first_v || s == r) continue;
                    if (std::gcd(a[r], a[s]) == 1) {
                        return Quadruple{first_u + 1, first_v + 1, r + 1, s + 1};
                    }
                }
            }
        }
        return std::nullopt;
    }

private:
    [[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;
    }

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

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

    if (const auto res = solver.solve(a)) {
        std::cout << "Found quadruple (1-based): ("
                  << res->u << ", " << res->v << ") and ("
                  << res->r << ", " << res->s << ")\n";
    } else {
        std::cout << "0\n";
    }
    return 0;
}

Proof of Completeness and Complexity

Theorem (Completeness and Soundness)

For any input array $a = (a_1, \dots, a_n)$, solve(a) returns a valid Quadruple if and only if $G$ contains a matching of size $2$, running in time

$$\mathcal{O}!\left(m \log m + n \log n + \sum_{i=1}^n 2^{\omega(a_i)}\right)$$

and $O(m + n \cdot 2^{\omega})$ space, where $m = \max_i a_i$.

Proof.

  1. Completeness of Search: Suppose a matching ${(u, v), (r, s)}$ exists in $G$. Without loss of generality, let $u = p_i$ and $v = p_j$ with $i < j$ in degree-sorted order. Since $(r, s)$ survives in $G \setminus {u, v}$, $\deg(p_i) + \deg(p_j) \le K$, so $j \le R(i)$ and $p_j \in A_i$. Since $\gcd(a_{p_i}, a_{p_j}) = 1$, the Möbius sum on $A_i$ is at least $1$, so the search loop must terminate on or before iteration $i$ with a valid first edge.
  2. Completeness of Reconstruction: For the chosen edge (first_u, first_v), $\deg(\text{first_u}) + \deg(\text{first_v}) \le K$, so $G \setminus {\text{first_u}, \text{first_v}}$ contains at least $K - (\deg(\text{first_u}) + \deg(\text{first_v}) - 1) \ge 1$ edge. Thus at least one vertex $r$ has $\deg_{\text{rem}}(r) > 0$, and the inner scan is guaranteed to find $s$.
  3. Time Complexity: Each vertex is inserted into active_mult at most once and removed at most once ($2 \sum_i 2^{\omega(a_i)}$ operations). The explicit std::gcd scan runs at most once during search and at most once during reconstruction ($O(n)$ total). $\square$