Coprime Pairs — Solution & Editorial

Back to the Problem

Möbius inversion: coprime pairs = ∑_d μ(d) · C(cnt-of-multiples-of-d, 2). Sieve μ and multiple-counts in O(V log V).

Complexity: O(V log V + N)

Watch out: Inclusion–exclusion directly double-counts; Möbius weights are what make it exact.