O(n sqrt n)
Can we do better than brute-force? We will need it to solve a follow up problem (check this post for intuition): 2183. Count Array Pairs Divisible by K.\n\n1. F
Can we do better than brute-force? We will need it to solve a follow up problem (check this post for intuition): [2183. Count Array Pairs Divisible by K](https://leetcode.com/problems/count-array-pairs-divisible-by-k/discuss/1784721/Count-GCDs).\n\n1. For each number, collect indexes in the increasing order.\n2. For a number, go through its indexes:\n\t- Track count of each `gcd(j, k)` we encountered so far in a map. \n\t- For each index `i`, check its `gcd(i, k)` agains GCDs for previous indices.\n\t\t- Add count to the result if `gcd(i, k) * gcd(j, k) % k == 0`.\n\n**C++**\n```cpp\nint countPairs(vector<int>& nums, int k) {\n    int res = 0;\n    unordered_map<int, vector<int>> m;\n    for (int i = 0;  i < nums.size(); ++i)\n        m[nums[i]].push_back(i);\n    for (auto &[n, ids] : m) {\n        unordered_map<int, int> gcds;\n        for (auto i : ids) {\n            auto gcd_i = gcd(i, k);\n            for (auto &[gcd_j, cnt] : gcds)\n                res += gcd_i * gcd_j % k ? 0 : cnt;\n            ++gcds[gcd_i];\n        }\n    }\n    return res;\n}\n```
[]