easy c++ solution O(nlogn) , using count of multiples and GCD
We know that a number n is divisible by a number m if ,\n   GCD(n,m) =m\n\nsimilarly   (nums[i] * nums[j]) is divisible by k if   their GCD is k .\nknowing this
We know that a number n is divisible by a number m if ,\n   GCD(n,m) =m\n\nsimilarly   (nums[i] * nums[j]) is divisible by k if   their GCD is k .\nknowing this if we just precalculate count of how many numbers are divisible by a number num( say) (for all num 1 to 10^5)\n\nthen we just need to loop for each element of array and finding out the remaing number( remaining_factor) needed to be multiplied  to it so as to make the GCD equals to k.\nthen for this number the count of pairs will be as much as the multiple of remaining_factor present in array (ignoring the number itself)\n\nThus adding count of pairs for each i in nums we will get our answer . we will have to divide the final answer by 2 as we have counted each pair twice for any pair (i , j) .\n\nTime -  O(n * log(n) )    // both finding the multiples for all i [0,n] and taking gcd for each element with k takes  nlogn time . so worst case time complexity is (nlogn) \n\nSpace -  O(n)   // we need two arrays of size n .\n\n```\nclass Solution {\npublic:\n    int count[100001];\n    int count_of_multiples[100001];\n    \n    long long coutPairs(vector<int>& nums, int k) {\n        int n=nums.size();\n\n        for(int i=0;i<n;i++)  count[nums[i]]++;  // counting frequency of elements\n        \n        for(int i=1;i<100001;i++){\n            for(int j=i;j<100001;j=j+i)  count_of_multiples[i]+=count[j]; //counting total elements present in array which are multiple of i\n        }\n        \n        long long ans=0;\n        for(int i=0;i<n;i++){\n            long long factor=__gcd(k,nums[i]);\n            long long remaining_factor= ( k / factor);\n            long long j = count_of_multiples[remaining_factor];\n            if(nums[i]%remaining_factor==0)j--;        // if nums[i] itself is multiple of remaining factor then we to ignore it as  i!=j\n            ans+=j;\n        }\n        \n        ans/=2;                                        // as we have counted any distinct pair (i,j) two times , we need to take them only once\n        return ans;\n    }\n};\n```
['C']