<p>Given a <strong>0-indexed</strong> integer array <code>nums</code> of length <code>n</code> and an integer <code>k</code>, return <em>the <strong>number of pairs</strong></em> <code>(i, j)</code> <em>such that:</em></p>

<ul>
	<li><code>0 &lt;= i &lt; j &lt;= n - 1</code> <em>and</em></li>
	<li><code>nums[i] * nums[j]</code> <em>is divisible by</em> <code>k</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5], k = 2
<strong>Output:</strong> 7
<strong>Explanation:</strong> 
The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.    
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4], k = 5
<strong>Output:</strong> 0
<strong>Explanation:</strong> There does not exist any pair of indices whose corresponding product is divisible by 5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], k &lt;= 10<sup>5</sup></code></li>
</ul>

import math
from collections import defaultdict

class Solution(object):
    def countPairs(self, nums, k):
        # Dictionary to store the frequency of gcds
        gcd_count = defaultdict(int)
        res = 0
        
        # Step 1: Count how many times each gcd with respect to k occurs
        for num in nums:
            gcd_num = math.gcd(num, k)
            gcd_count[gcd_num] += 1

        # Step 2: Iterate over all pairs of gcds whose product is divisible by k
        gcds = list(gcd_count.keys())
        
        for i in range(len(gcds)):
            for j in range(i, len(gcds)):
                if gcds[i] * gcds[j] % k == 0:
                    # If i == j, we count pairs from the same gcd bucket
                    if i == j:
                        res += gcd_count[gcds[i]] * (gcd_count[gcds[i]] - 1) // 2
                    else:
                        res += gcd_count[gcds[i]] * gcd_count[gcds[j]]
        
        return res

30300