Simple Number Theory solution using GCD concept.
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\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)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n        vector<int> newArr;\n        long long int ans = 0; int pos = nums.size()-1;\n        map<int, int> exists;\n        int maxVal = -1;\n        for(int i=0;i<nums.size();i++) {\n            maxVal = max(maxVal, nums[i]);\n            if(nums[i]%k==0) {\n                ans += pos;\n                pos--;\n            } else {\n                int gcd = __gcd(nums[i], k);\n                if(gcd != 1) {\n                    newArr.push_back(nums[i]);\n                    exists[nums[i]]++;\n                }\n            }\n        }\n        map<int,long long > alreadyCal;\n        sort(newArr.begin(), newArr.end());\n        for(int i=0;i<newArr.size();i++) {\n            exists[newArr[i]]--;\n            int reminder = k/(__gcd(k, newArr[i]));\n            if(i>0&&newArr[i]==newArr[i-1]) {\n                if((long long)((long long)newArr[i]*(long long)newArr[i])%k==0)\n                    alreadyCal[newArr[i]]--;\n                if(alreadyCal[newArr[i]]>0)\n                ans += alreadyCal[newArr[i]];\n                continue;\n            }\n            int next = ((newArr[i]/reminder)*reminder)+(newArr[i]%reminder != 0 ? reminder: 0);\n            for(int j=next;j<=maxVal;j+=reminder) {\n                if(j<newArr[i]) continue;\n                if(exists[j]) {\n                    ans+=exists[j];\n                    alreadyCal[newArr[i]]+=exists[j];\n                }\n                \n            }\n        }\n        return ans;\n    }\n};\n```
['Number Theory', 'C++']