Using Contribution Technique Along with GCD,Divisors Logic
IntuitionThe minimum number which needed to be multiplied can be calculated as k/gcd(k,nums[i]) for all elementsApproachSolution Strategy:Divisor Counting Techn
# Intuition
The minimum number which needed to be multiplied can be calculated as k/gcd(k,nums[i]) for all elements

# Approach
Solution Strategy:

Divisor Counting Technique:

Instead of checking every pair directly (which would be O(n²)), we use a smart divisor counting approach
For each number, find its divisors
Track the frequency of each divisor across the array
Dynamically update divisor counts


Key Mathematical Insight:

For a pair (nums[i], nums[j]) to be divisible by k, we need to find a multiplier that completes the divisibility
Use GCD (Greatest Common Divisor) to calculate the required multiplier
requiredMultiplier = k / gcd(k, nums[i])


Optimization Techniques:

Find divisors in O(sqrt(num)) time
Avoid nested loops
Use frequency-based counting to reduce time complexity



Algorithmic Steps:

Initialize a divisor count vector
For each number:

Find and count its divisors
Increment divisor frequencies


For each number again:

Remove its own divisors from the count
Calculate required multiplier
Add count of valid multipliers to answer

# Complexity
- Time complexity:
O(nsqrt(n))

- Space complexity:
O(n)

# Code
```cpp []
#define ll long long

class Solution {
public:
    long long countPairs(vector<int>& nums, int k) {
        ll ans = 0;
        ll n = nums.size();
        
        vector<ll>divisorCount(100005,0);

        for(auto &num:nums){
            for(int i=1;i*i<=num;i++){
                if(num%i==0){
                    divisorCount[i]++;
                    if((num/i)!=i)divisorCount[num/i]++;
                }
            }
        }
        //for(auto &i:divisorCount)cout<<i.first<<" "<<i.second<<endl;
        for(auto &num:nums){
            for(int i=1;i*i<=num;i++){
                if(num%i==0){
                    divisorCount[i]--;
                    if((num/i)!=i)divisorCount[num/i]--;
                }
            }
            ll requiredMultiplier=k/(__gcd(k,num));
            //cout<<requiredMultiplier<<" ";
            ans+=divisorCount[requiredMultiplier];
            //ans+=numCount[requiredMultiplier];
        }
        return ans;
    }
};
```
['C++']