C++11 in 30 lines save GCDs to unordered_map 124ms
e.g.\n[1,2,3,4,5]\nas same as\n[1,2,1,2,1]\nas same as\n1 appear 3 time\n2 appear 2 time\narray [0...k] O(k^2)\nuse map to reduce time further:\nmap O(sqrt(k)^2
e.g.\n[1,2,3,4,5]\nas same as\n[1,2,1,2,1]\nas same as\n1 appear 3 time\n2 appear 2 time\narray [0...k] O(k^2)\nuse map to reduce time further:\nmap O(sqrt(k)^2)\n\ncase k=15 (3*a, 5*b) is legal\n\ntraverse i,j in map:\nself cnt[i]*(cnt[i]-1)/2\nother cnt[i]*cnt[j]\n\n```\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n        long long ret = 0;\n\n        unordered_map<int, int> cnt;\n        for (auto num : nums) {\n            //printf("%d \\n", __gcd(k, num));\n            cnt[__gcd(k, num)]++;\n        }\n\n        for (auto [i,cnti] : cnt) {\n            if (cnt[i] == 0) continue; // TLE if not continue\n            for (auto [j,cntj] : cnt) {\n                if (j < i) continue; // dup\n                if (((long long)i*j)%k) continue; // WA\n                if (i == j) {\n                    //printf("cnt[%d]=%d %d\\n", i, cnt[i], cnt[i]-1);\n                    ret += (long long)cnt[i] * (cnt[i]-1) /2;\n                } else {\n                    //printf("cnt[%d]=%d cnt[%d]=%d\\n", i, cnt[i], j, cnt[j]);\n                    ret += (long long)cnt[i] * cnt[j];\n                }\n            }\n        }\n\n        return ret;\n    }\n};\n```
[]