ACTUAL EXPLANATIONS and DRY RUN of what we do and  WHY WE DO IT THIS WAY?
I doubt anyone understands how and why the solution works, and if you are someone like me who is struggling, this is for you.\n\nI read up extensively, did dry 
I doubt anyone understands how and why the solution works, and if you are someone like me who is struggling, this is for you.\n\nI read up extensively, did dry runs and then came to an understanding of how to solve similar questions\n\nBig writeup ahead, hope it helps!\n\n# Initial Thoughts:\n\n- this is a hard question for a reason and involves a gcd counting trick, that is not something you can come up with on the spot\n- Its not even intuitive, but once you understand this, it is easy to remember, and can help solve future problems\n- We need to take all pairs, get their gcds, sort it and then run queries on it\n- We definitely cannot look at all pairs in a nested loop cuz of constraints\n- Picking an index after getting all gcds, also means sorting and then returning\n- Since nums can be max of 5*10^4, this means that is the max gcd we will be dealing with\n- So if we can count for each number from 1 to nums_max, how many pairs have a gcd[i] where 1<=i<=nums_max\n- Then we can easily run queries on it. Because then all gcds are sorted, we will have a gcd[i] array where all index are gcds and gcd[i] are count of pairs\n\n# Intuition on Binary Search:\n\n- suppose we wanna find 5th index of sorted gcds, how would we do it\n- consider gcd[] = [0,2,5,6,6,7]. we ignore index 0, since 0 cannot be a gcd\n- gcd of 1 is a gcd of 2 pairs. gcd=2 of 5 pairs. Remember index is the gcd and gcd[i] is the count\n- so what will be the gcd value at index 8? we have 2 pairs of gcd 1, 5 pairs of gcd 2 and 6 pairs of gcd 3\n- So if we write down the gcds and sort it, we get something like [1,1,2,2,2,2,2,3,3,3,3,3,3]. Take the 8th index we get 3.\n- Notice what we did, we basically counted like a prefix sum, and then found the position where 8 can get inserted\n- So if we generate a prefix sum array of gcd counts, we can do a binary search and find the answer to queries.\n- so prefix = [0,2,7,13,19...] for 8th index, we see that 8th value will lie between 7 and 13. So that has gcd[i] where i = gcd = 3\n- Since we want the 8th value, we want to find the prefix count x where x >= 8. 7 wont work. 8 and above will work. But we need smallest such x.\n- This is how we will binary search\n\n# Intuition on Counting GCDs:\n- Now lets look at counting the gcds of pairs\n- take eg: [4,4,2,1]. We have pairs (4,4), (4,2), (4,1), (4,2), (4,1), (2,1)\n- and gcds as 4,2,1,2,1,1. Sorted = [1,1,1,2,2,4]. 3 pairs have gcd = 1, 2 pairs have gcd=2 and 1 pair has gcd=4\n- Since we know max number will be 4, max gcd will be 4. We will start building gcd[] in reverse\n- Why reverse is good? Because no number less than 4 will have a gcd of 4, that is obvious because gcd is greatest common divisor.\n- 4 cannot divide a number < 4.\n- So now 4 can only be gcd of 2 numbers that are 4 or more. Actually since gcd is greatest divisor, it means one number HAS to be 4.\n- Also, the other number will ALWAYS be a multiple of 4. This is an observation that is so simple and obvious but tricky to come up with\n- So now we wanna form pairs with a number that is 4, and another number that is multiple of 4\n- If we are counting numbers with gcd 4, and wanna check if there are numbers in the array that are multiples of 4\n- The easiest way is to create a frequency counter map of all numbers to quickly get the count of numbers\n- So our freq map for example is freq = {1:1, 2:1, 4:2}\n- So we start reverse from 4. And we count all numbers that are 4 or multiples of 4, because only they will have a gcd of 4\n- Here we get count = 2.\n- Now we need to find out how many pairs can we form with 2 numbers. Its easy to see only 1 pair, but what if count is big, whats an easy way to find it?\n- nC2 = n!/( (n-2)!. 2! ) = n(n-1)/2. Memorize this, its a useful formula.\n- so for gcd = 4, we have count = 2 and pairs = 2(1)/2 = 1\n- 1 pair that has a gcd 4\n- so gcd = [0,0,0,0,1] index 0 is ignored\n- now we come to i = 3, we have 0 numbers and 0 pairs of numbers that have gcd=3\n- gcd = [0,0,0,0,1]\n- Now for i = 2. We count numbers that are 2 or multiples of 2. We get count = 3\n- pairs = 3(2)/2 = 3\n- So 3 pairs of numbers have gcd = 2\n- Lets verify this first. one number has to be 2 and other a multiple. SO looking at input [4,4,2,1]\n- we get pairs (2,4), (2,4) and.... thats only 2 pairs, but our formula gave us 3.\n- Remember the gcd at 4 had a pair (4,4) and when we counted the pairs, we counted (4,4) which is wrong\n\n# Inclusion Exclusion Principle:\n\n- This is the inclusion exclusion principle that is at work here.\n- Lets look at it briefly\n- Inclusion Exclusion Principle is a counting technique where we count elements satisfying a property\n- while making sure we dont double count elements that satisfy both properties\n- Say we wanna count number of people having at least 1 dog or 1 cat.\n- We add up the total number of people having cats and dogs and subtract the people having both cat and dog both\n- In sets A U B = A + B - (A intersect B)\n- This can be extended to more elements\n-- A U B U C = A + B + C - (A intersect B) - (A intersect B) - (A intersect B) + (A intersect B intersect C)\n- This can be generalized to A U B U ... X -> but that is deep into maths and out of scope for me\n\n# Applying the exlusion principle:\n\n- So now we know we double counted gcd pair (4,4).\n- In fact if we had a number 8, gcd of 4 will include a pair of (4,8)\n- And if we find gcd of 2, we will look at multiples of 2 which are 2,4,6,8. And again choosing pairs will count pair of (4,8)\n- So after counting pairs, of say gcd i, we need to subtract counts gcds of every multiple of 2 starting from 2nd multiple\n- so initially we counted pairs (2,4), (2,4), (2,8), but then also had included pairs (4,4) and (4,8) and any other pairs if there were more multiples present\n - So we need to remove counts of pairs we double counted, and these would be counts at each multiple of 2, starting from 4.\n- So 5 - 2 = 3. We removed (4,4) and (4,8) which were double counted, and anyways their gcd is 4. Not 2\n- So coming to our example, for i=2, we had pairs = 3\n- Then we loop from 2nd multiple of 2 = 4->gcd_max\n- And subtract counts. So subtract gcd[4] = 4\n- Pairs = 3-1 = 2. And gcd = [0,0,2,0,1]\n- Now for i = 1. We count numbers = 4. Pairs = 4.3/2 = 6\n- Now subtract from every 2nd multiple of 1. So subtract 2,3,4 = 6-2-1 = 3\n- So there are 3 pairs with gcd = 3\n- Which are (1,2), (1,4), (1,4)\n\n# Explanation on Binary Search:\n\n- Now gcd = [0,3,2,0,1]\n - As discussed above we create a prefix sum array = [0,3,5,5,6]\n- And queries = [5,3,1,0]. Remember we need the 5th index when all gcds are sorted, not 5th count\n- Lets write the gcd sorted = [1,1,1,2,2,4]. So 5th index is 4. We need to go an index higher. So bisect right is best for this\n- So in our case, we are to find 5th index. Means we are looking for gcd where count becomes 6 or more\n- That means if we do bisect right at 5, it will return the rightmost index where (count = 5) + 1\n- count basically signifies indices. If gcd 1 has a count 5. Means there are 5 indices where gcd = 1\n- Then if we see that gcd 2 has a prefix count of 7. Means gcd 1 and 2 have a combined total count of pairs = 7\n- And since we determined, because of index to count relation, we need to go +1\n- So if we bisect right for given query value, say 5. We will end up at gcd where count becomes > 5, and this will be lowest index where count > 5\n- So we can easily binary search and find ans = [4,2,1,1] which is correct according to given example\n\n\n\n# Time complexity:\n- O(mlogm + qlogm) where q = queries length, m is max_num <= 5*10^4\n- We look at every query and do a binary search over array of size m so qlogm \n- The for loop is doing a harmonic skip, the outer loop runs for m times, but every iteration, we dont look at all m numbers\n- if suppose we have m numbers, and the first iteration looks at all m numbers\n- next one looks at m/2 numbers, next m/3 and so on\n- This will have a time complexity of m/1 + m/2 + m/3 +... m/m = m(1/1 + 1/2 + 1/3 + ... 1/m) = mlogm\n- This is harmonic sequence and involves maths, interested readers can look it up\n- There are other small time factors we ignore, like to build the counter map, finding the max number and building the prefix array\n- These take O(n + m + m) time but are smaller than logm so we ignore it. Here n = length of nums\n- So total time: O(mlogm + qlogm)\n\n# Space complexity:\n- space: O(m + n) for prefix sum array, and counter freq map\n\n\n# Code\n```python3 []\nclass Solution:\n    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:\n        \n\n        max_gcd = max(nums)\n        # counter = collections.Counter(nums) # freq count of numbers, can do manually too\n        # Counter does slow down the python code on leetcode especially\n        # Tried with a defaultdict and normal dict, both gave similar results\n        # So prefer to use defaultdict\n        counter = collections.defaultdict(int)\n        for n in nums:\n            counter[n] += 1\n\n        gcd = [0] * (max_gcd + 1) # we wanna reach index of max_gcd\n\n        for i in range(max_gcd, 0, -1): # go from max_gcd -> 1\n            count = 0 # count of numbers that are i or multiples of i\n            for j in range(i, max_gcd + 1, i): # since we need multiples of i, add step of i\n                count += counter[j]\n\n            # now we find the total pairs we can form and add that to gcd\n            gcd[i] = count * (count - 1) // 2\n\n            # now use exclusion to remove double counted pairs\n            # This starts from 2nd multiple of i\n            for j in range(2 * i, max_gcd + 1, i):\n                gcd[i] -= gcd[j]\n\n        # now prefix sum array\n        prefix = [0] * (max_gcd + 1)\n        curr = 0\n        for i in range(1, max_gcd + 1):\n            curr += gcd[i]\n            prefix[i] += curr\n\n        # now process the queries\n        res = []\n        for q in queries:\n            res.append(bisect.bisect_right(prefix, q))\n\n            # we will implement our binary search for practice\n            # This is also slower on leetcode, so prefer to use bisect when you can\n            # But remember, might be asked to implement the binary search, so keep practicing\n            # lo, hi = 1, max_gcd + 1\n            # while lo < hi:\n            #     mid = lo + (hi - lo) // 2\n            #     if prefix[mid] <= q: # look higher. Remember, we want mid = gcd that is just greater than where we find q. So if <= q, this doesnt have our answer and we look higher\n            #         lo = mid + 1\n            #     else: # but if prefix[mid] > q, we wanna look lower and this CAN be our answer, cuz we want smallest gcd where prefix > q\n            #         hi = mid # ending up with hi = mid, means dont need +1 in mid calc\n            # res.append(lo)\n\n        return res\n```
['Math', 'Binary Search', 'Counting', 'Prefix Sum', 'Python3']