Introduction

The brute-force way to count co-prime pairs from two arrays checks every pair and calls gcd, which costs O(n x m) pair checks. When the arrays are large, a faster approach is to count how many values are divisible by each integer and then use the Möbius function to include and exclude shared factors efficiently.

Turn Pairwise GCD Checks Into Divisor Counting

Suppose you have arrays A and B, and you want the number of pairs (a, b) such that gcd(a, b) = 1. Instead of checking each pair directly, count how many values in each array are divisible by d for every d up to the maximum value.

If count_a[d] is the number of elements in A divisible by d, and count_b[d] is the same for B, then:

• 'count_a[2] x count_b[2] counts pairs sharing factor 2'
• 'count_a[3] x count_b[3] counts pairs sharing factor 3'
• but pairs sharing both 2 and 3 get counted more than once

This is exactly the kind of overlap that inclusion-exclusion handles. The Möbius function gives a compact way to do that over all divisors.

Use the Möbius Function

The key identity is:

coprime_pairs = sum(mu[d] x count_a[d] x count_b[d])

for all d from 1 to max_value, where mu[d] is the Möbius value of d.

The Möbius function works like this:

• 'mu[1] = 1'
• 'mu[d] = 0 if d contains any squared prime factor'
• otherwise mu[d] is 1 or -1 depending on whether d has an even or odd number of distinct prime factors

This lets you add and subtract divisor counts so that only pairs with greatest common divisor equal to 1 remain in the final total.

A Runnable Python Implementation

The implementation below uses a linear sieve to compute Möbius values, then counts multiples for both arrays.

1from collections import Counter
2
3def mobius_up_to(limit):
4    mu = [0] * (limit + 1)
5    mu[1] = 1
6    primes = []
7    is_composite = [False] * (limit + 1)
8
9    for i in range(2, limit + 1):
10        if not is_composite[i]:
11            primes.append(i)
12            mu[i] = -1
13        for p in primes:
14            if i * p > limit:
15                break
16            is_composite[i * p] = True
17            if i % p == 0:
18                mu[i * p] = 0
19                break
20            mu[i * p] = -mu[i]
21
22    return mu
23
24def count_coprime_pairs(a, b):
25    limit = max(max(a), max(b))
26    mu = mobius_up_to(limit)
27
28    freq_a = Counter(a)
29    freq_b = Counter(b)
30
31    count_a = [0] * (limit + 1)
32    count_b = [0] * (limit + 1)
33
34    for d in range(1, limit + 1):
35        for multiple in range(d, limit + 1, d):
36            count_a[d] += freq_a[multiple]
37            count_b[d] += freq_b[multiple]
38
39    total = 0
40    for d in range(1, limit + 1):
41        total += mu[d] * count_a[d] * count_b[d]
42
43    return total
44
45A = [2, 3, 4, 9]
46B = [5, 6, 8]
47
48print(count_coprime_pairs(A, B))

For these sample arrays, the function counts only the pairs whose greatest common divisor is 1.

Why This Is Faster Than O(n x m)

Let M be the largest value in either array.

The main work is:

• computing Möbius values up to M
• building frequencies
• iterating over multiples for each divisor

The divisor-multiple loops cost about O(M log M), which is far better than checking every pair when n x m is much larger than the value range. This is especially effective when the arrays are long but the integers are not enormous.

That tradeoff is important: this method depends more on maximum value than on the number of pair combinations.

When to Use This Technique

This approach is a good fit when:

• array values are positive integers
• the maximum value is manageable
• you need the total count, not the explicit list of co-prime pairs

If the values are extremely large and sparse, the divisor table may become too expensive in memory or time, and a different strategy may be needed. But for many contest and interview-style constraints, Möbius inversion is the standard subquadratic solution.

Common Pitfalls

• Using Euler's totient function directly for this problem. Totients count numbers co-prime to one value, but the pair-counting formula here is based on Möbius inversion.
• Forgetting that the fast method assumes positive integers. Zero and negative values need separate handling rules.
• Mixing up array length with maximum value in the complexity analysis. The speedup comes from shifting the cost toward divisor enumeration up to M.
• Building count_a and count_b by scanning the full arrays for every divisor. Frequency tables are important for keeping the method efficient.
• Expecting this approach to list the co-prime pairs. It counts them, but it does not enumerate each pair explicitly.

Summary

• The naive solution checks every pair and becomes too slow on large inputs.
• A faster method counts divisibility by each integer and combines those counts with the Möbius function.
• The formula sum(mu[d] x count_a[d] x count_b[d]) returns the number of co-prime pairs.
• This reduces the problem from pairwise comparison to divisor-based aggregation.
• The technique is most effective when the maximum array value is moderate compared with the number of possible pairs.