Golang binary search
Intuition\n\nGoal is to fill gcdCount, where gcdCount[i] is the number of pairs with GCD[i]. Then we can simply use binary search to efficiently find queries.\n
# Intuition\n\nGoal is to fill gcdCount, where gcdCount[i] is the number of pairs with GCD[i]. Then we can simply use binary search to efficiently find queries.\n\n# Code\n```golang []\n\nfunc gcdValues(nums []int, queries []int64) []int {\n    m := 0\n\n    for _, v := range nums {\n        if v > m {\n            m = v\n        }\n    }\n\n    gcdCount := make([]int, m+1)\n    divisors := make([]int, m+1)\n\n    for _, v := range nums {\n        for i := 1; i <= int(math.Sqrt(float64(v))); i++ {\n            if v%i == 0 {\n                divisors[i]++\n                if v/i != i {\n                    divisors[v/i]++\n                }\n            }\n        }\n    }\n\n    for i := m; i >= 1; i-- {\n        n := divisors[i]\n        paircount := (n * (n - 1)) / 2\n        multiple := i * 2\n        for multiple <= len(gcdCount)-1 {\n            paircount -= gcdCount[multiple]\n            multiple += i\n        }\n        gcdCount[i] = paircount\n    }\n\n    intervals := [][]int{}\n    for i := range gcdCount {\n        val := gcdCount[i]\n        if val > 0 {\n            if len(intervals) == 0 {\n                intervals = append(intervals, []int{0, val - 1, i})\n            } else {\n                top := intervals[len(intervals)-1]\n                intervals = append(intervals, []int{top[1] + 1, top[1] + val, i})\n            }\n        }\n    }\n    res := make([]int, len(queries))\n    for idx, q := range queries {\n        left := 0\n        right := len(intervals) - 1 \n        for left <=  right {\n            mid := left + (right - left)/2\n            inter := intervals[mid] \n            if int(q) >= inter[0] && int(q) <= inter[1] {\n                res[idx] = inter[2]\n                break \n            } else if int(q) < inter[0] {\n                right = mid - 1\n            } else {\n                left = mid + 1\n            }\n        }\n    }\n\n\n    return res\n}\n```
['Go']