different approach | C++
Intuition\n Describe your first thoughts on how to solve this problem. \nI tried to simulate number of pairs with a^b = k problem in this. I try to find the sma
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI tried to simulate number of pairs with a^b = k problem in this. I try to find the smallest number which when multiplied by a number will be divisible by k. I calculate by this by lcm(num,k)/num. Then i count all the index which have this smallest number in them. I can do this by keeping track of factors of every number i process.\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(k)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    long long LCM(int a, int b){\n        long long x = a * 1LL * b;\n        long long y = (long long)__gcd(a,b);\n        return x/y;\n    }\n    long long countPairs(vector<int>& nums, int k) {\n        int n = nums.size();\n        long long cnt = 0;\n        unordered_map<int, long long> mp;\n        for(auto it : nums){\n            int need = (int)(LCM(it,k)/(long long)it);\n            cnt += mp[need];\n            for (int i=1; i<=sqrt(it); i++)\n            {\n                if (it%i == 0)\n                {\n                    if (it/i == i)\n                        mp[i]++;\n                    else{\n                        mp[i]++;\n                        mp[it/i]++;\n                    }\n                }\n            }\n        }\n        return cnt;\n    }\n};\n```
['C++']