Easy C++ Solution with T.C :- O(N*Log N).
\nclass Solution {\npublic:\n    #define ll long long \n    ll gcd(ll a,ll b){\n        if(b==0) return a;\n        return gcd(b,a%b);\n    }\n    \n    long lo
```\nclass Solution {\npublic:\n    #define ll long long \n    ll gcd(ll a,ll b){\n        if(b==0) return a;\n        return gcd(b,a%b);\n    }\n    \n    long long countPairs(vector<int>& nums, int k) {\n        unordered_map<ll,ll> mp;\n        ll n=nums.size();\n        for(ll i=0;i<n;++i){\n            mp[nums[i]]++;\n        }\n        ll mx =1e5+10;\n        vector<ll> mul(mx,0);\n        for(ll i=1;i<mx;++i){\n            for(ll j=i;j<mx;j+=i){\n                if(mp.find(j) != mp.end()){\n                    mul[i] += mp[j];\n                }\n            }\n        }\n        ll ans=0;\n        k = 1LL*k;\n        for(ll i=0;i<n;++i){\n            ll gcd1 = gcd((ll)nums[i],k);\n            ll r = k/gcd1;\n            if(nums[i]%r == 0) ans += (mul[r]-1);\n            else ans += mul[r];\n        }\n        return ans/2;\n    }\n};\n```
['Math', 'C']