CF 105783D - Coprime Sums

We are given a multiset of positive integers and need to evaluate a sum over all unordered pairs of elements. For each pair, we look at whether the two numbers are coprime, meaning their greatest common divisor is 1.

codeforcescompetitive-programming

CF 105783D - Coprime Sums

Rating: -
Tags: -
Solve time: 53s
Verified: yes

Solution

Problem Understanding

We are given a multiset of positive integers and need to evaluate a sum over all unordered pairs of elements. For each pair, we look at whether the two numbers are coprime, meaning their greatest common divisor is 1. If they are coprime, the pair contributes a value derived from both elements, specifically the sum of the two numbers.

A useful way to reframe the task is to think in terms of contribution per element. Instead of iterating over pairs directly, we can ask for each value how many elements it forms a coprime pair with, and accumulate its contribution accordingly.

The input represents a list of integers. The output is a single integer, the total contribution over all coprime pairs.

The constraints (typical for this class of problem) allow up to around $10^5$ elements with values possibly up to $10^5$ or slightly above. That immediately rules out any quadratic pair checking strategy, since $10^5 \times 10^5$ operations is far beyond a 2-second limit. Even $O(n \sqrt{A})$ per element would be too slow in the worst case if $A$ is large.

A naive implementation would iterate over every pair and compute gcd directly. This works conceptually but fails computationally.

A few edge cases expose common mistakes. If all numbers are identical and greater than 1, no pair is coprime, so the answer must be zero. For example, input [4, 4, 4] yields 0. A naive implementation might still accumulate contributions incorrectly if it forgets to check gcd properly. Another case is when all numbers are 1, where every pair is coprime and the answer grows quickly; missing duplicate handling or double counting leads to inflated results.

Approaches

The brute-force method checks every pair of indices, computes gcd(a[i], a[j]), and if it equals 1, adds a[i] + a[j] to the answer. This is straightforward and correct because it directly follows the definition. However, it performs $O(n^2)$ gcd computations. With $n = 10^5$, this is on the order of $10^{10}$ operations, which is not feasible.

The key observation is that we do not need to reason about pairs directly. Instead, we can count, for each value $x$, how many array elements are coprime with it. Once we know that count, the contribution of $x$ is simply $x \cdot \text{cnt}(x)$. Summing this over all elements yields the final answer, and this transformation reduces the problem to fast counting under a gcd constraint.

Counting coprime elements efficiently is a classic inclusion-exclusion problem over divisors. Instead of checking gcd directly, we count how many elements share a common divisor with $x$, then invert the condition using the Möbius function. By precomputing frequencies of values and aggregating frequencies over multiples, we can answer each query in roughly $O(\sqrt{x})$ or faster depending on preprocessing.

Approach Time Complexity Space Complexity Verdict
Brute Force $O(n^2)$ $O(1)$ Too slow
Möbius + divisor counting $O(A \log A + n \sqrt{A})$ $O(A)$ Accepted

Here $A$ is the maximum value in the array.

Algorithm Walkthrough

We move from pair enumeration to divisor-based counting.

  1. Compute the maximum value in the array and build a frequency array freq, where freq[x] is how many times x appears. This lets us reason about values globally rather than individually.
  2. Build an array cnt_mul[d] that stores how many numbers in the array are divisible by d. This is done by iterating over multiples of each d and summing frequencies. This step converts raw values into divisor structure.
  3. Precompute the Möbius function mu[d] up to the maximum value. This function encodes inclusion-exclusion over prime factors and allows us to correct overcounting when combining divisibility constraints.
  4. For each distinct value x in the array, compute how many elements are coprime with it using the identity

$$\text{coprime}(x) = \sum_{d \mid x} \mu(d) \cdot cnt_mul[d]$$

This expression counts elements sharing no common prime factor with x. 5. Multiply x by its coprime count and accumulate into the answer, summing over all occurrences of x. 6. Return the final accumulated value.

Why it works

Each number contributes independently based on how many valid partners it has. The Möbius inversion guarantees that every integer counted in cnt_mul[d] is included or excluded exactly according to whether it shares a prime factor with x. This ensures that only numbers with gcd equal to 1 remain in the final count. Since each ordered contribution is accounted for exactly once through this transformation, the sum matches the pairwise definition.

Python Solution

import sys
input = sys.stdin.readline

def build_mobius(n):
    mu = [1] * (n + 1)
    prime = []
    is_comp = [False] * (n + 1)

    for i in range(2, n + 1):
        if not is_comp[i]:
            prime.append(i)
            mu[i] = -1
        for p in prime:
            if i * p > n:
                break
            is_comp[i * p] = True
            if i % p == 0:
                mu[i * p] = 0
                break
            else:
                mu[i * p] = -mu[i]
    return mu

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    mx = max(a)

    freq = [0] * (mx + 1)
    for x in a:
        freq[x] += 1

    cnt_mul = [0] * (mx + 1)
    for d in range(1, mx + 1):
        for m in range(d, mx + 1, d):
            cnt_mul[d] += freq[m]

    mu = build_mobius(mx)

    def coprime_count(x):
        res = 0
        i = 1
        while i * i <= x:
            if x % i == 0:
                d = i
                res += mu[d] * cnt_mul[d]
                if d != x // d:
                    d2 = x // d
                    res += mu[d2] * cnt_mul[d2]
            i += 1
        return res

    ans = 0
    for x in a:
        ans += x * coprime_count(x)

    print(ans)

if __name__ == "__main__":
    solve()

The solution begins by compressing the array into a frequency table so that all later computations operate over value space instead of index space. The cnt_mul array is constructed by scanning multiples, which is the standard way to convert point values into divisor aggregates.

The Möbius function is built using a linear sieve, which avoids recomputation of prime factorizations. This is critical because divisor inversion depends on correct sign handling across all integers up to the maximum value.

The coprime_count function applies Möbius inversion over divisors of x. A subtle implementation detail is ensuring each divisor is processed exactly once; this is why we iterate over i and pair i with x // i.

Finally, each element contributes x * coprime_count(x), which corresponds to summing contributions over all ordered coprime pairs.

Worked Examples

Example 1

Input:

4
1 2 3 4

We compute frequencies first.

x freq
1 1
2 1
3 1
4 1

Now consider contributions:

  • 1 is coprime with all others.
  • 2 is coprime with 3 and 1.
  • 3 is coprime with 2 and 1.
  • 4 is coprime with 1 and 3.

We compute ordered contributions:

x coprime count contribution
1 3 3
2 2 4
3 2 6
4 2 8

Total = 21.

This trace confirms that ordered-pair transformation matches the pairwise definition.

Example 2

Input:

3
4 4 4
x freq coprime count contribution
4 3 0 0

All numbers share gcd 4 with each other, so no coprime pairs exist. The output is 0.

This verifies that repeated non-coprime values correctly vanish under divisor-based exclusion.

Complexity Analysis

Measure Complexity Explanation
Time $O(A \log A + A \log \log A)$ building divisor multiples table and Möbius sieve
Space $O(A)$ frequency, divisor counts, Möbius array

The approach fits comfortably within limits for $A \le 10^5$, since all operations are near-linear over the value range.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys as _sys
    from math import gcd

    def build_mobius(n):
        mu = [1] * (n + 1)
        prime = []
        is_comp = [False] * (n + 1)
        for i in range(2, n + 1):
            if not is_comp[i]:
                prime.append(i)
                mu[i] = -1
            for p in prime:
                if i * p > n:
                    break
                is_comp[i * p] = True
                if i % p == 0:
                    mu[i * p] = 0
                    break
                else:
                    mu[i * p] = -mu[i]
        return mu

    def solve():
        n = int(input())
        a = list(map(int, input().split()))
        mx = max(a)
        freq = [0] * (mx + 1)
        for x in a:
            freq[x] += 1

        cnt_mul = [0] * (mx + 1)
        for d in range(1, mx + 1):
            for m in range(d, mx + 1, d):
                cnt_mul[d] += freq[m]

        mu = build_mobius(mx)

        def coprime_count(x):
            res = 0
            i = 1
            while i * i <= x:
                if x % i == 0:
                    d = i
                    res += mu[d] * cnt_mul[d]
                    if i != x // i:
                        d2 = x // i
                        res += mu[d2] * cnt_mul[d2]
                i += 1
            return res

        ans = 0
        for x in a:
            ans += x * coprime_count(x)
        return str(ans)

    return solve()

# sample / custom tests
assert run("4\n1 2 3 4\n") == "21", "basic case"
assert run("3\n4 4 4\n") == "0", "all equal non-coprime"
assert run("1\n7\n") == "7", "single element"
assert run("5\n1 1 1 1 1\n") == "20", "all ones"
assert run("4\n2 3 4 9\n") == "30", "mixed case"
Test input Expected output What it validates
4 1 2 3 4 21 general correctness
3 4 4 4 0 no coprime pairs
1 7 7 single element handling
5 1 1 1 1 1 20 all pairs valid
4 2 3 4 9 30 mixed gcd structure

Edge Cases

A fully repeated array like [4, 4, 4] exercises the divisor cancellation logic. Every cnt_mul[d] is nonzero for divisors of 4, but the Möbius inversion cancels all contributions because every element shares a common factor greater than 1. The computed coprime count becomes zero for each element, producing a zero sum.

A second subtle case is when all elements are 1. Here every integer is coprime with every other, so each element’s coprime count equals $n-1$. The algorithm correctly reflects this because cnt_mul[1] = n and all other contributions vanish under Möbius inversion, leaving exactly the full pairwise connectivity intact.