29ms: mostly not my work, but I can understand
Intuition\n\nFor each pair, calculated its GCD. However, it has a poor time complexity O(n^2log(n)) where the question is intended to reject such kind of soluti
# Intuition\n\nFor each pair, calculated its GCD. However, it has a poor time complexity $$O(n^2log(n))$$ where the question is intended to reject such kind of solution.\n\nIt is a maths problem more than an engineering problem.\n\nTo eliminate $$n$$ out of $$n^2$$ in time complexity of comparing each pair, the formula `n * (n - 1) / 2` should be used, where `n` is the frequency of a factor among numbers in `nums`.\n\nTo eliminate $$log(n)$$ in time complexity of a trival GCD calculation, combinations of a GCD is calcuclated from combinations of a factor  among numbers in `nums` excluding combinations of the GCD\'s multiples.\n\nNumber of combination of number pairs that have GCD == 1 is calculated from total number of all combinations minus total number of other combinations (GCD > 1).\n\n# Approach\n\n1. Calculate frequency of each number in `nums`\n   `vFreq_num[i] = std::count(nums.begin(), nums.end(), i);`\n2. Calculate frequency of a factor among numbers in `nums`\n   `vFreq_factor[i] = vFreq_num[i] + vFreq_num[i * 2] + ...`\n3. Calculate combinations of number pair that has a common factor\n   `vNumOfComb_factor[i] = vFreq_factor[i] * (vFreq_factor[i] - 1) / 2`\n4. Calculate combinations of number pair that has a greatest common factor\n   `vNumOfComb_gcd[i] = vNumOfComb_factor[i] - vNumOfComb_factor[i * 2] - vNumOfComb_factor[i * 3] - ...`\n5. Transform `vNumOfComb_gcd` into stacked form and compress it (dense form instead of sparse) for lengthy `queries`\n6. Reply to `queries` using `std::upper_bound` function\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```cpp []\nclass Solution\n{\npublic:\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries);\n};\n\nstd::vector<int> Solution::gcdValues(std::vector<int>& nums, std::vector<long long>& queries)\n{\n\tint const nNum_max = std::accumulate(nums.begin(), nums.end(), 0, [](int const lhs, int const rhs)->int\n    {\n        return std::max(lhs, rhs);\n    });\n\n\tstd::vector<long long> vGcdFreq((size_t)(1 + nNum_max), 0ll);\n\n    // 1. frequency of each number\n\tfor (int num : nums)\n\t{\n\t\tvGcdFreq[num]++;\n\t}\n\n    // 2. frequency of each number and its multiples\n\tfor (int nCommonFactor = 2; nCommonFactor <= nNum_max; ++nCommonFactor)\n\t{\n\t\tlong long nCount = vGcdFreq[nCommonFactor];\n\t\tfor (int nMultipleOfCommonFactor = nCommonFactor + nCommonFactor; nMultipleOfCommonFactor <= nNum_max; nMultipleOfCommonFactor += nCommonFactor)\n\t\t{\n\t\t\tnCount += vGcdFreq[nMultipleOfCommonFactor];\n\t\t}\n\t\tvGcdFreq[nCommonFactor] = nCount;\n\t}\n\n    // 3. combinations of each number excluding that of its multiples -- equivalent to combinations of GCD\n    // 4. transform "combinations of GCD" into accumulated form -- for binary search in queries\n\tlong long const n = (long long)nums.size();\n\tlong long const llTotalCombination = n * (n - 1) / 2;\n\tlong long llAccumulator = 0;\n\tstd::vector<std::tuple<long long, int>> vKiosk;\n\tvKiosk.reserve(vGcdFreq.size());\n\tfor (int nCommonFactor = nNum_max; 2 <= nCommonFactor; --nCommonFactor)\n\t{\n\t\tlong long llCount = vGcdFreq[nCommonFactor] * (vGcdFreq[nCommonFactor] - 1) / 2;\n\t\tfor (int nMultipleOfCommonFactor = nCommonFactor + nCommonFactor, nMultipleOfCommonFactor_last = nNum_max; nMultipleOfCommonFactor <= nMultipleOfCommonFactor_last; nMultipleOfCommonFactor += nCommonFactor)\n\t\t{\n\t\t\tllCount -= vGcdFreq[nMultipleOfCommonFactor];\n\t\t}\n\t\tvGcdFreq[nCommonFactor] = llCount;\n\n\t\tif (llCount)\n\t\t{\n            // REMARK: we are constructing `vKiosk` in descending order\n\t\t\tvKiosk.emplace_back(llTotalCombination - llAccumulator, nCommonFactor);\n\n\t\t\tllAccumulator += llCount;\n\t\t}\n\t}\n//\tvGcdFreq[1] = llTotalCombination - llAccumulator;\n    vKiosk.emplace_back(llTotalCombination - llAccumulator, 1);\n\n    // 5. answer to queries\n\tstd::vector<int> vResult;\n\tvResult.reserve(queries.size());\n\n\tfor (long long const query : queries)\n\t{\n        // REMARK: `vKiosk` is constructed in descending order\n\t\tvResult.push_back(std::get<int>(*std::upper_bound(vKiosk.rbegin(), vKiosk.rend(), std::make_tuple(query), [](auto const &lhs, auto const &rhs)->bool\n\t\t\t{\n\t\t\t\treturn std::get<long long>(lhs) < std::get<long long>(rhs);\n\t\t\t})));\n\t}\n\n\treturn vResult;\n}\n\n#include <iostream>\nstatic auto _______ = []() {\n    // turn off sync\n    std::ios::sync_with_stdio(false);\n    // untie in/out streams\n    std::cin.tie(nullptr);\n    return 0;\n}();\n\n```
['Combinatorics', 'C++']