[C++] O(n * sqrt(10^5)) time, O(10^5) space.
\n/*\n\n(pair_left, pair_right)\nWe enumerate the pair_left from end to start, and try to find how many pair_right are valid.\n\nFor example, a = [30, 14, 19] a
```\n/*\n\n(pair_left, pair_right)\nWe enumerate the pair_left from end to start, and try to find how many pair_right are valid.\n\nFor example, a = [30, 14, 19] and k = 3 * 5 * 7 = 105.\nFor 30, we only care about the largest divisor which is 15, that 105 % 15 = 0, \nand we then try to find 105/15 = 7, how many a[i] such that a[i] % 7 = 0.\n\nNote below i, j, x are not same as in the code.\n\nWe use c[i] to represent how many a[j] in the array a such that a[j] % i = 0 and k % i = 0.\n\nFor each a[i] from end to start, we find the largest number x, such that k % x = 0 and a[i] % x = 0.\nWe only care about the largest x, such that k/x is the lowest requirement for all pair_right a[j] such as a[j] % (k/x) = 0.\nSo for current pair_left which is a[i], the final result should add c[k/x].\n*/\n\nclass Solution {\npublic:\n    long long coutPairs(vector<int>& a, int k) {\n        long long ret = 0;\n        vector<int>c(100005, 0);\n        int n = a.size();\n        for(int i = n-1;i>=0;i--){\n\t\t    // UPDATE: small improvement.\n            int x = __gcd(a[i], k);\n            int mx = 0;\n            // use tmp to save, so we don\'t need to do the loop again.\n            vector<int>tmp;\n            for(int j = 1;j*j<=x;j++){\n               if(x%j==0){\n                    int tt = j;\n                    mx = max(mx, tt);\n                    tmp.push_back(tt);\n                    tt = x/j;\n                    if(tt!=j){\n                        mx = max(mx, tt);\n                        tmp.push_back(tt);\n                    }\n                }\n            }\n            if(mx!=0){\n                ret += c[k/mx];\n            }\n            for(auto tt : tmp)c[tt]++;\n        }\n        return ret;\n    }\n};\n```
['C']