GCD based Theory || C++ Solution
Approach\n- Smallest number which should be multiplied with nums[i] so that the product is divisible by k is k / gcd(k, nums[i]).\n- Once gcd(k, nums[i]) is fou
# Approach\n- Smallest number which should be multiplied with nums[i] so that the product is divisible by k is k / gcd(k, nums[i]).\n- Once gcd(k, nums[i]) is found, keep track of occurrences of similar gcds using map and add to total count of pairs.\n\n# Complexity\n- Time complexity:$$O(n*sqrt(k))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n        map<long long, int> mp;\n        long long count=0, gcdVal;\n        for(int i=0; i<nums.size(); i++)\n        {\n            gcdVal = gcd(nums[i], k);\n            for(auto x: mp)\n            {\n                if((gcdVal*x.first)%k==0)\n                    count+=x.second;\n            }\n            //not placed before iterating map as it will count extra pairs for 0-indexed element\n            mp[gcdVal]++;\n        }\n        return count;\n    }\n};\n```
['Number Theory', 'C++']