# 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)$.