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:
- 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.
- 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:
| |
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$.