Go Solution | Inclusion-exclusion Principle | Prefix Sum | Binary Search
Intuition\nPreprocess to find the number of times each GCD occurs. Then get the answer by using binary search.\n\n# Complexity\n- Time complexity: $O(U\text{log
# Intuition\nPreprocess to find the number of times each GCD occurs. Then get the answer by using binary search.\n\n# Complexity\n- Time complexity: $O(U\\text{log}U), U=max(nums)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(U)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```golang []\nfunc gcdValues(nums []int, queries []int64) []int {\n\tmx := slices.Max(nums)\n\tfreq := make([]int, mx+1)\n\tfor _, v := range nums {\n\t\tfreq[v]++\n\t}\n\tcntGcd := make([]int, mx+1)\n\tfor i := mx; i > 0; i-- {\n\t\tvar c int\n\t\tfor j := i; j <= mx; j += i {\n\t\t\tc += freq[j]\n\t\t\tcntGcd[i] -= cntGcd[j]\n\t\t}\n\t\tcntGcd[i] += c * (c - 1) / 2 // select two numbers from c numbers\n\t}\n\tfor i := 2; i <= mx; i++ {\n\t\tcntGcd[i] += cntGcd[i-1] // prefix sum\n\t}\n\tans := make([]int, len(queries))\n\tfor i, query := range queries {\n\t\tans[i] = sort.SearchInts(cntGcd, int(query)+1)\n\t}\n\treturn ans\n}\n```
['Math', 'Binary Search', 'Prefix Sum', 'Go']