3404. Count Special Subsequences

You are given an array nums consisting of positive integers.

A special subsequence is defined as a subsequence of length 4, represented by indices (p, q, r, s), where p < q < r < s. This subsequence must satisfy the following conditions:

• nums[p] * nums[r] == nums[q] * nums[s]
• There must be at least one element between each pair of indices. In other words, q - p > 1, r - q > 1 and s - r > 1.

A subsequence is a sequence derived from the array by deleting zero or more elements without changing the order of the remaining elements.

Return the number of different special subsequences in nums.

class Solution {
public:
    long long numberOfSubsequences(vector<int>& nums) {
        map<pair<int,int>,int> freq;
        auto gcdPair = [&](int i, int j) {
            int g = __gcd(nums[i], nums[j]);
            return pair<int,int>{nums[i] / g, nums[j] / g};
        };
        
        long long res = 0, n = nums.size();
        for(int r = 4; r < n; r++) {
            for(int s = r + 2; s < n; s++) {
                freq[gcdPair(s,r)]++;
            }
        }
        for(int q = 2; q < n; q++) {
            for(int p = 0; p + 1 < q; p++) {
                res += freq[gcdPair(p,q)];
            }
            for(int r = q + 2, s = r + 2; s < n; s++) {
                freq[gcdPair(s,r)]--;
            }
        }
        return res;
    }
};