C++ | O(nsqrt(n)) | Commented
\nclass Solution {\npublic:\n    int mx = 1e5 + 5;\n    void update(vector<long long>& divisors, int num) {\n\t\t//update divisors of num\n        for(int i = 1
```\nclass Solution {\npublic:\n    int mx = 1e5 + 5;\n    void update(vector<long long>& divisors, int num) {\n\t\t//update divisors of num\n        for(int i = 1; i * i <= num; i++) {\n            if(num % i == 0) {\n                if(i == num / i) divisors[i]++;\n                else {\n                    divisors[i]++;\n                    divisors[num/i]++;\n                }\n            }\n        }\n    }\n    long long coutPairs(vector<int>& nums, int k) {\n        vector<long long> divisors(mx, 0LL);\n        long long res = 0LL;\n        for(int i = 0; i < nums.size(); i++) {\n\t\t\t//number to be multiplied with num[i] to make it divisible by k\n            int r = k / (__gcd(nums[i], k));\n\t\t\t\n\t\t\t//numbers with divisors r\n            res += (long long)divisors[r];\n\t\t\t\n\t\t\t//update the divisors of num[i]\n            update(divisors, nums[i]);\n        }\n        return res;\n    }\n};\n```
[]