C++ : GCD, Factors and Upper Bound
\nclass Solution {\npublic:\n    #define ll long long\n    long long coutPairs(vector<int>& nums, int k) {\n        int n = nums.size();\n        ll cnt = 0;// 
```\nclass Solution {\npublic:\n    #define ll long long\n    long long coutPairs(vector<int>& nums, int k) {\n        int n = nums.size();\n        ll cnt = 0;// cnt variable to store the ans\n        \n        vector<int > f;// vector to store the factors of k\n        for (int i=1; i<=sqrt(k); i++)\n        {\n            if (k%i == 0)\n            {\n                if (k/i == i)\n                    f.push_back(i);\n                else \n                {\n                    f.push_back(i);\n                    f.push_back(k/i);\n                }\n            }\n        }\n        \n        map<int, vector<int>> mp;// map to store the index of element in vector corresponding to their factors\n        for(int i=0;i<n;i++)\n        {\n            for(int j=0;j<f.size();j++)\n            {\n                if(nums[i]%f[j]==0)\n                    mp[f[j]].push_back(i);\n            }\n        }\n\t\t\n        for(int i=0;i<n;i++)// traversing through each element in nums\n        {\n            if(nums[i]%k==0)// if nums[i] is divisible by k, then it can pair with all element ahead of it\n            {\n                cnt+=(ll)(n-i-1);\n            }\n            else // we it will pair with all elements which has factor k/gcd(nums[i],k)\n            {\n                int x1 = gcd(nums[i],k);\n                auto it = upper_bound(mp[k/x1].begin(),mp[k/x1].end(),i);\n                int idx = it-mp[k/x1].begin();\n                cnt+=(ll)(mp[k/x1].size()-idx);\n            }\n        }\n        return cnt;// returning the ans\n    }\n};\n```
['C']