如何高效求解长度为n的两数组中Gcd(a[i],b[j])=1的数对数量

Alright, let's figure out how to count the number of pairs (a[i], b[j]) where their GCD is 1, without resorting to the slow O(n²) brute force approach. Here's a solid plan using Mobius function and sieve methods that runs in way better time complexity.

Step 1: Reframe the Problem with Inclusion-Exclusion #

Instead of checking every pair directly, we can leverage the inclusion-exclusion principle (via the Mobius function) to compute valid pairs efficiently. The core idea is:

• We don't need to count coprime pairs one by one. Instead, we can calculate how many elements in b are coprime with each element in a using divisor properties and the Mobius function, which encodes the inclusion-exclusion signs for us.

Step 2: Precompute the Mobius Function #

The Mobius function μ(d) is key here—it helps us apply inclusion-exclusion without manually tracking every prime combination. It's defined as:

• μ(d) = 1 if d is a square-free number with an even number of distinct prime factors.
• μ(d) = -1 if d is a square-free number with an odd number of distinct prime factors.
• μ(d) = 0 if d has any squared prime factor (like 4=2², 12=2²×3).

We can compute μ for all numbers up to the maximum value in either array using a linear sieve (O(M) time, where M is the largest number in a or b).

Step 3: Count Frequencies and Divisor Multiples in Array b #

First, create a frequency array freq where freq[x] is how many times x appears in b. Then, compute cnt[d]—the total number of elements in b divisible by d. We do this with a sieve-like loop: for each d, iterate through all its multiples and sum their frequencies. This runs in O(M log M) time.

Step 4: Calculate Valid Pairs for Each Element in a #

For each element x in a, the number of elements in b that are coprime with x is given by:
sum(μ(d) * cnt[d]) for all divisors d of x.

This works because the Mobius function automatically handles the inclusion-exclusion logic: we subtract counts of numbers divisible by each prime factor of x, add back counts divisible by products of two primes, subtract products of three, etc.—exactly what we need to count coprimes.

Full Implementation Example (Python) #

def compute_mobius(max_num):
    mobius = [1] * (max_num + 1)
    is_prime = [True] * (max_num + 1)
    primes = []
    for p in range(2, max_num + 1):
        if is_prime[p]:
            primes.append(p)
            mobius[p] = -1
        for q in primes:
            if p * q > max_num:
                break
            is_prime[p * q] = False
            if p % q == 0:
                mobius[p * q] = 0
                break
            else:
                mobius[p * q] = mobius[p] * mobius[q]
    mobius[0] = 0
    return mobius

def count_coprime_pairs(a, b):
    if not a or not b:
        return 0
    
    max_val = max(max(a), max(b))
    mobius = compute_mobius(max_val)
    
    # Count frequency of each number in b
    freq = [0] * (max_val + 1)
    for num in b:
        freq[num] += 1
    
    # Compute cnt[d]: number of elements in b divisible by d
    cnt = [0] * (max_val + 1)
    for d in range(1, max_val + 1):
        for multiple in range(d, max_val + 1, d):
            cnt[d] += freq[multiple]
    
    total = 0
    for x in a:
        # Find all divisors of x
        divisors = set()
        for i in range(1, int(x**0.5) + 1):
            if x % i == 0:
                divisors.add(i)
                divisors.add(x // i)
        # Calculate sum of mobius[d] * cnt[d] for all divisors d
        current = 0
        for d in divisors:
            current += mobius[d] * cnt[d]
        total += current
    
    return total

# Example usage:
a = [2, 3, 5]
b = [4, 6, 7]
print(count_coprime_pairs(a, b))  # Output: 4 (Valid pairs: (2,7), (3,7), (5,4), (5,7))

Time Complexity Breakdown #

• Precomputing Mobius function: O(M)
• Calculating cnt array: O(M log M) (the sum of M/d for d=1 to M is O(M log M))
• Processing each element in a: O(n * sqrt(x)) (each number has at most ~2*sqrt(x) divisors)

This is far better than O(n²)—even for n=1e5 and M=1e5, this runs in acceptable time, whereas O(n²) would be computationally infeasible.

Edge Cases to Consider #

• If a contains 0: GCD(0, k) = k, so pairs with 0 are valid only if b[j] = 1. Add a check for x=0 in the loop over a, and add cnt[1] (count of 1s in b) instead of computing divisors.
• Duplicate elements: The frequency array handles duplicates naturally, as we count all occurrences of each number in b.

内容的提问来源于stack exchange，提问作者Amish Sharma