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)$.
| |
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$:
- Evaluate $\sum_{d \mid a_{p_i}} \mu(d),M_i[d]$ in $O(2^{\omega(a_{p_i})})$ operations.
- 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.
- 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:
| |
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.
- 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.
- 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$. - Time Complexity: Each vertex is inserted into
active_multat most once and removed at most once ($2 \sum_i 2^{\omega(a_i)}$ operations). The explicitstd::gcdscan runs at most once during search and at most once during reconstruction ($O(n)$ total). $\square$