2183. Count Array Pairs Divisible by K

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) such that:

• 0 <= i < j <= n - 1 and
• nums[i] * nums[j] is divisible by k.

• Time : O(n*sqrt(k))
• Space : O(n)

class Solution {
    unordered_map<int, int> divisor;
    void update(int n) {
        int i = 1;
        for(; i * i < n; i++) {
            if(n % i == 0){
                divisor[i] += 1;
                divisor[n/i] += 1;
            }
        }
        if(i * i == n)
            divisor[i] += 1;
    }

    int gcd(int p, int q) {
        return q == 0 ? p : gcd(q, p % q);
    }

public:
    long long countPairs(vector<int>& nums, int k) {
        long long res = 0;
        int prv = 0;
        for(auto n : nums) {
            if(n % k == 0) {
                res += nums.size() - 1 - prv;
                prv++;
            } else {
                int g = gcd(n,k);
                res += divisor[k/g];
                update(n);
            }
        }
        return res;
    }
};