C++/Rust: Breaking the Problem into Sub-problems
Intuition\n Describe your first thoughts on how to solve this problem. \nLet m be: 1 + maxmmum element of nums.\n\nWe divide the problem into three sub-problems
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet m be: 1 + maxmmum element of nums.\n\nWe divide the problem into three sub-problems:\n1) Calculating the divisor frequency vector<int> freq(n), where freq[d] means that there are exact freq[d] items in nums that could be devided by d.\n2) Calculating the gcd vector<int64_t> cnt(n), where cnt[d] means that there are exact cnt[d] pair of <i, j> (i < j) such that d = gcd(nums[i], nums[j]).\n3) Calculating the answers to the queries.\n  \n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO((M * SQRT(M) + N)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(M)\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {\n        int m = 1 + *max_element(nums.begin(), nums.end());\n        \n        // solving problem #1\n        vector<int> freq(m);\n        for (auto a: nums) {\n            for (int t = 1; t * t <= a; ++t) {\n                if (a % t != 0) continue;\n                freq[t] += 1;\n                if (t * t == a) continue;\n                freq[a / t] += 1;\n            }\n        }\n\n        // solving problem #2\n        vector<int64_t> cnt(m);\n        for (int d = m - 1; d > 0; --d) {\n            // calculating the total number of pairs that having\n            // d as a common divisor\n            cnt[d] = (int64_t)freq[d] * (freq[d] - 1) / 2;\n            \n            // this is a crtical step of the solution to\n            // the whole problem\n            // it reduces the count that corresponding to those\n            // common divisors that are not GCD\'s \n            for (int it = 2 * d; it < m; it += d) {\n                cnt[d] -= cnt[it];\n            }\n        }\n\n        // solving problem #3\n        vector<int64_t> sum(m);\n        vector<int> ret;\n\n        // build prefix-sum array \n        for (int d = 1; d < m; ++d) {\n            sum[d] = sum[d - 1] + cnt[d];\n        }\n         \n        // binary search for the answers\n        for (auto q: queries) {\n            ret.push_back(lower_bound(sum.begin(), sum.end(), q + 1) - sum.begin());\n        }\n\n        return ret;\n    }\n};\n```\n\n```\n//Rust\nimpl Solution {\n    pub fn gcd_values(nums: Vec<i32>, queries: Vec<i64>) -> Vec<i32> {\n        let m = 1 + (*nums.iter().max().unwrap()) as usize;\n        let mut cnt = vec![0i64; m];\n        for a in nums {\n            let a = a as usize;\n            for t in 1 ..= a {\n                if t * t > a { break }\n                if a % t != 0 { continue }\n                cnt[t] += 1;\n                if t * t == a { break }\n                cnt[a / t] += 1;\n            }\n        }\n\n        for d in (1 .. m).rev() {\n            cnt[d] = cnt[d] * (cnt[d] - 1) / 2;\n            for it in 2 ..= (m - 1) / d {\n                cnt[d] -= cnt[it * d];\n            }\n        }\n\n        let mut sum = vec![0i64; m];\n        let mut ret = vec![];\n        for d in 1 .. m {\n            sum[d] = sum[d - 1] + cnt[d];\n        } \n        for q in queries {\n            let q = q + 1;\n            let mut left = 1;\n            let mut right = m - 1;\n            while left < right {\n                let mid = left + (right - left) / 2;\n                if sum[mid] < q {left = mid + 1; }\n                else            { right = mid; }\n            }\n            ret.push(left as i32);\n        }\n        \n        ret \n    }\n}\n```
['Binary Search', 'Prefix Sum', 'C++', 'Rust']