Python Solution: Efficient GCD Pair Counting with Möbius Function and Inclusion–Exclusion
IntuitionThe direct calculation of pairs for each GCD value by checking every possible pair would be inefficient. The key is to leverage number-theoretic insigh
# Intuition\nThe direct calculation of pairs for each GCD value by checking every possible pair would be inefficient. The key is to leverage number-theoretic insights, specifically the M\xF6bius function and the Inclusion\u2013Exclusion Principle, to count how many pairs have a given GCD without enumerating all pairs directly.\n\nThe M\xF6bius function $$\\mu$$ helps decompose the count of pairs divisible by certain factors into a combination that yields the count of pairs with an exact GCD. This transforms a complex counting problem into a more manageable one, supported by precomputed values.\n\n# Approach\n1. **M\xF6bius Function Precomputation**:  \n   Use a sieve (similar to the Sieve of Eratosthenes) to compute the M\xF6bius function $$\\mu(n)$$ for all $$1 \\leq n \\leq M$$, where $$M = \\max(\\text{nums})$$.\n\n2. **Divisor Frequency Calculation**:  \n   For each number in `nums`, increment the frequency of all its divisors. Store these frequencies in $$\\text{factors}[d]$$, which represents how many numbers from `nums` are divisible by $$d$$.\n\n3. **Counting Pairs by GCD**:\n   - To find the number of pairs with $$\\gcd = k$$:\n     - Start with the count of pairs divisible by $$k$$.\n     - Adjust this count using Inclusion\u2013Exclusion to remove those pairs whose GCD is actually a multiple of $$k$$ (like $$2k, 3k, \\dots$$).  \n     The M\xF6bius function $$\\mu(m)$$ indicates whether to add or subtract the counts of pairs divisible by $$mk$$.\n\n   Formally:\n   $$\n   \\text{Pairs with } \\gcd = k = \\sum_{j=1}^{\\lfloor M/k \\rfloor} \\mu(j) \\times \\frac{\\text{factors}[j \\times k] \\times (\\text{factors}[j \\times k] - 1)}{2}\n   $$\n\n   Here, $$\\mu(j)$$ ensures we add or subtract counts in the correct manner.\n\n4. **Prefix Sum for Queries**:\n   After computing the number of pairs for each possible GCD $$k$$, build a prefix sum array $$\\text{check}[i]$$ where:\n   $$\n   \\text{check}[i] = \\sum_{k=1}^{i} (\\text{# of pairs with gcd } = k).\n   $$\n\n   This allows answering queries quickly. If a query asks "How many pairs have $$\\gcd \\leq q$$?", we can simply return $$\\text{check}[q]$$.\n\n**In summary:**  \n- Use the M\xF6bius function and divisor counting to efficiently calculate pairs by exact GCD.\n- Store partial results and handle queries with prefix sums and binary search.\n\n# Complexity\n- **Time Complexity**:  \n  - Computing the M\xF6bius function: $$O(M \\log(\\log M))$$\n  - For each number, factor counting up to $$\\sqrt{M}$$ worst case: $$O(N \\sqrt{M})$$ in a naive scenario.\n  - Counting pairs using the M\xF6bius function and Inclusion\u2013Exclusion: $$O(M)$$ for iterating through all $$k \\leq M$$.\n  \n  Overall, the complexity can vary based on the input size and distribution, but typically it will be efficient enough for reasonably large inputs.\n\n- **Space Complexity**:  \n  - Storing M\xF6bius array and frequencies: $$O(M)$$\n  - Additional data structures (prefix sums, factors): $$O(M)$$\n\n  Thus, total space complexity is around $$O(M)$$.\n\n# Code\n```python3 []\nfrom collections import defaultdict, Counter\nfrom bisect import bisect_right\nfrom typing import List\n\nclass Solution:\n    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:\n        # Step 1: Prepare basic parameters\n        max_n = max(nums)  # M\n        mob = [1] * (max_n + 1)\n        is_prime = [True] * (max_n + 1)\n        \n        # Step 2: Compute the M\xF6bius function using a sieve\n        for i in range(2, max_n + 1):\n            if is_prime[i]:\n                for j in range(i, max_n + 1, i):\n                    is_prime[j] = False\n                    mob[j] *= -1\n                for j in range(i * i, max_n + 1, i * i):\n                    mob[j] = 0\n        \n        # Count frequencies of each number\n        freq = Counter(nums)\n        nums = list(freq.items())  # (num, frequency)\n\n        # Step 3: Compute factors array\n        # factors[d] = how many numbers in nums are divisible by d\n        factors = defaultdict(int)\n        for (num, f) in nums:\n            # For each num, find its divisors\n            # O(N * sqrt(M)) worst case\n            limit = int(num**0.5)\n            for m in range(1, limit+1):\n                if num % m == 0:\n                    factors[num // m] += f\n                    if m != num // m:\n                        factors[m] += f\n\n        # Step 4: Define a function to find the number of pairs with gcd = k\n        def find_k_pair_num(k):\n            # Start with pairs divisible by k\n            total = (factors[k] * (factors[k]-1)) // 2\n            \n            # Inclusion\u2013Exclusion using M\xF6bius function\n            # Subtract/add pairs divisible by multiples of k\n            for i in range(2*k, max_n+1, k):\n                total += mob[i//k] * ((factors[i] * (factors[i]-1)) // 2)\n            \n            return total\n\n        # Step 5: Precompute cumulative counts\n        check = [0] * (max_n+1)\n        for i in range(1, max_n+1):\n            check[i] = check[i-1] + find_k_pair_num(i)\n\n        # Step 6: Answer queries\n        # Each query q asks: how many pairs have gcd <= q?\n        # Since check[i] stores cumulative count up to i, we use binary search:\n        ans = []\n        for q in queries:\n            ans.append(bisect_right(check, q))\n        \n        return ans\n\n```
['Python3']