1. Problem Understanding

We are given an array of $n$ positive integers and asked to count the number of non-empty subsets such that the greatest common divisor (GCD) of all elements in the subset is exactly $1$. In other words, we need to identify those subsets in which the numbers, when taken together, are "co-prime" in the sense that no divisor greater than $1$ can evenly divide all of them. Since checking every subset by brute force is infeasible for $n$ as large as $10^5$, an efficient combinatorial and number-theoretic approach, often employing inclusion-exclusion or its related concept, Möbius inversion, must be used.

2. Solution Analysis

The idea is to leverage the properties of divisibility and the principle of inclusion-exclusion. Here is a step-by-step breakdown:

• Step 1: Counting Subsets with Divisibility Constraints
  For every integer $d$, consider counting the number of non-empty subsets where every number in the subset is divisible by $d$. Let $f(d)$ be the number of such subsets.
  If we denote by $\text{freq}[d]$ the number of elements in the array that are multiples of $d$, then the number of possible non-empty subsets is:
  $f(d) = 2^{\text{freq}[d]} - 1$
  This formula holds because each element that is a multiple of $d$ can either be chosen or not, and we subtract $1$ to exclude the empty subset.

• Step 2: Using Möbius Inversion
  Notice that a subset with $\gcd = 1$ will be counted in $f(1)$ but might also be over-counted in $f(d)$ for other divisors $d > 1$.
  The Möbius function $\mu(d)$ helps correct for this over-counting. By Möbius inversion, the number of valid subsets (with $\gcd = 1$) is given by:
  $\text{Answer} = \sum_{d=1}^{\text{max}} \mu(d) \cdot f(d)$
  where the summation is taken over all possible divisors $d$ up to some maximum value (which can be assumed as the maximum value in the input array), and $\mu(d)$ is defined as:

  • $\mu(d) = 1$ if $d$ is a square-free positive integer with an even number of prime factors.
  • $\mu(d) = -1$ if $d$ is a square-free positive integer with an odd number of prime factors.
  • $\mu(d) = 0$ if $d$ has a squared prime factor.

• Step 3: Preprocessing Step
  To efficiently compute $f(d)$ for all relevant $d$, count the numbers in the array which are divisible by $d$. This can be done by:

  1. Computing the frequency of each element in the given array.
  2. Iterating over each divisor $d$ up to the maximum number and summing up frequencies for multiples of $d$.

• Step 4: Modular Arithmetic
  Since the answers can be very large, and we need to report the result modulo $10^9+7$, all arithmetic operations (especially when computing powers of $2$) must be performed modulo $10^9+7$.

3. Time and Space Complexity Analysis

• Time Complexity:

  • Counting frequencies requires $O(n)$ time.
  • The divisor aggregation process iterates over all divisors for each number up to the maximum value (which is up to $10^5$) and hence takes approximately $O(M \log M)$ where $M$ is the maximum value among array elements.
  • Precomputing the Möbius function via a sieve-like method takes $O(M \log \log M)$.
  • Calculating modular exponents for each divisor takes constant time on average (using fast exponentiation), leading to a total time close to $O(M)$ operations.
    Overall, the approach works in $O(M \log M)$ time, which is acceptable for $M = 10^5$.

• Space Complexity:

  • The additional space used is for the frequency array and auxiliary arrays for the Möbius function and $f(d)$, each of size $O(M)$.
    Therefore, the space complexity is $O(M)$.