Simple O(Nsqrt(N)) Solution|| c++ || With Explanation
I have created an array muls  in which muls[i] is the count of multiples of i in the nums. \nWe will simply iterate through each element and find what\'s the ma
I have created an array muls  in which muls[i] is the count of multiples of i in the nums. \nWe will simply iterate through each element and find what\'s the maximum it can contribute so that product become k...ofcourse it will be gcd of nums[i] and k. Then we will find the multiple of k/gcd which has already occurred.\n\n```\nclass Solution {\npublic:\n    long long coutPairs(vector<int>& nums, int k) {\n        vector<int>muls(100001,0);\n        int n=nums.size();\n        long long int ans=0;\n        for(int i=0;i<n;i++)\n        {\n            int g=__gcd(nums[i],k);\n            ans+=(muls[k/g]);\n            for(int j=1;j<=int(sqrt(nums[i]));j++) //for finding divisors of nums[i]\n            {\n                if(nums[i]%j==0)\n                {\n                    int div2=nums[i]/j;\n                    muls[j]++;\n                    if(j!=div2)\n                    {\n                        muls[div2]++;\n                    }\n                }\n            }\n        } \n        return ans;\n    }\n};
[]