Efficient GCD Queries with Frequency Counting and Overcount Elimination
Complexity\n- Time complexity: O(N+max(nums)+log(max(nums))*Queries)\n\n- Space complexity:O(max(nums))\n\n# Code\npython3 []\nclass Solution:\n    def gcdValue
# Complexity\n- Time complexity: $$O(N+max(nums)+log(max(nums))*Queries)$$\n\n- Space complexity:$$O(max(nums))$$\n\n# Code\n```python3 []\nclass Solution:\n    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:\n        n = len(nums)\n        counter = Counter(nums)  # O(n)\n        maxi = max(nums)  # O(n)\n\n        # Count how many numbers are divisible by each i\n        freq = [0] * (maxi + 1) # O(max(nums))\n        for i in range(1, maxi + 1):  # O(max(nums))\n            multiplicant = 1\n            numCount = 0\n            while multiplicant * i <= maxi:\n                multiple = multiplicant * i\n                numCount += counter[multiple]\n                multiplicant += 1\n            freq[i] = numCount\n\n        # nC2 - no. of pairs formed from each freq\n        freq = [(x) * (x - 1) // 2 for x in freq]  # O(max(nums))\n\n        # Remove overcounts for multiples of i\n        for i in reversed(range(1, maxi + 1)):  # O(max(nums))\n            multiplicant = 2  # 2i, 3i, ...\n            while multiplicant * i <= maxi:\n                freq[i] -= freq[multiplicant * i]\n                multiplicant += 1\n\n        # print(list(range(maxi + 1)))\n        # print(freq)\n\n        cum_freq = list(accumulate(freq))  # O(max(nums))\n        # print(cum_freq)\n\n        # ind+1 as it is 0-based indexing\n        # bisect_left is lowerbound -> smallest index <= x\n        # but not upper bound -> smallest index > x (bisect_right)\n        res = [\n            bisect_left(cum_freq, ind + 1) for ind in queries\n        ]  # O(log(max(nums))*queries)\n\n        return res\n\n```
['Array', 'Hash Table', 'Math', 'Binary Search', 'Combinatorics', 'Counting', 'Python3']