"Optimized Pair Counting Using a Sieve-Like Approach & GCD Trick – LeetCode 2183 🚀"
IntuitionIntuitionThe problem requires counting pairs
(𝑖,𝑗) such that:This can be rewritten as:Rearranging, we need:(v[i]×v[j]) to be divisible by kUsing proper
# Intuition

# Intuition
The problem requires counting pairs 
(𝑖,𝑗) such that:

    lcm(𝑣[𝑖],𝑣[𝑗]) mod 𝑘=0
This can be rewritten as:

    (𝑣[𝑖]×𝑣[𝑗]) / gcd⁡(𝑣[𝑖],𝑣[𝑗])mod 𝑘=0 

Rearranging, we need:

(v[i]×v[j]) to be divisible by k

Using properties of divisibility and LCM-GCD relationships, this means:

v[i]×v[j] should be divisible by k
Rearranging, it suffices that:

    𝑣[𝑗] should be a multiple of 𝑘/gcd⁡(𝑘,𝑣[𝑖])

# Approach

Precompute Factors & Divisibility Counts:

First, determine the frequency of each number in v using contains[].
Use divs[] to store the number of values in v that are divisible by a given number.
Build Adjacency List:

For every number e in v, store all its divisors in adj[e].
Compute Valid Pairs Efficiently:

Iterate over the array v, and for each element e, compute x = k / gcd(k, e).
The count of numbers that are multiples of x in v is stored in divs[x].
Decrease the count of numbers divisible by each divisor of e before counting valid pairs to avoid self-pairing

# Complexity Analysis
Precomputing Frequencies & Building Adjacency List:

Counting elements in contains[] → O(n)
Constructing divs[] and adj[]:
Iterates over divisors up to max(v), which takes O(n log m) (where m = max(v))
Iterating Over Array and Counting Pairs:

For each e in v, updating divs[] and computing valid pairs involves iterating over its divisors, which takes O(log m).
The loop runs n times, giving O(n log m).
Total Complexity:

O(n log m) + O(n log m) = O(n log m)
Space Complexity: O(m + n) (for contains[], divs[], and adj[]).
This approach ensures an efficient solution compared to a brute force O(n²) method. 🚀

# Code
```cpp []

class Solution {
    #define ll long long
public:
    long long countPairs(vector<int>& v, int k) {
        ll res=0,mx=*max_element(v.begin(),v.end());
        vector<ll>contains(mx+1);
        vector<ll>divs(max(mx,(ll)k)+1);

        unordered_map<ll,vector<ll>>adj;

        for(auto it : v){
            contains[it]++;
        }

        for(int i=1;i<=mx;i++){
            for(int j=i;j<=mx;j+=i){
                divs[i]+=contains[j];
                adj[j].push_back(i);
            }
        }


        for(auto e : v){
            ll x=k/__gcd(k,e);
            for(auto f : adj[e]){
                divs[f]--;
            }
            res+=divs[x];
        }
        return res;
    }
};
```
['C++']