[for beginners] How to conquer this problem, some key points explanation
In my opinion, the key points are:\n\n1. the length of all the divisors (or maybe it\'s called factors) of k, would be very small. especially consider the lengt
In my opinion, the key points are:\n\n1. the length of all the divisors (or maybe it\'s called factors) of k, would be **very small**. especially consider the length of original array nums, 1e5. (you could check other posts for a specific academic estimation of this length if you are interested, now assuming it is m).\n\n2. therefore, instead of checking every pair of nums, which n^2 would be 1e10, we could naturally think of another idea: let the gcd(greatest common divisor) of (each number, k) represent that number, ignore other useless information, and only finding suitable pairs based on their gcds.\n\n3. to get every gcd of a number and k, if you don\'t know the gcd API, my idea was like, o(k) to get all the divisors, 1e5, and just one pass of all the divisors from greatest to smallest to find gcd. (remember m, the length of total divisors, is significantly small). Therefore, finding each number\'s gcd would be o(n * m)\n\n```\nvoid getGcdArr(int k, vector<int> &gcd, unordered_map<int, int> &m) {\n        int id = 0;\n        gcd.push_back(1);\n        m[1] = 0;\n        for (int i = 2; i <= k / 2; i++) {\n            if (k % i == 0) {\n                gcd.push_back(i);\n                m[i] = ++id;\n            }\n        }\n        gcd.push_back(k);\n        m[k] = ++id;\n    }\n    int getGcd(int num, vector<int> &gcd) {\n        int n = gcd.size();\n        for (int i = n - 1; i >= 0; i--) {\n            if (num % gcd[i] == 0) {\n                return i;\n            }\n        }\n        return 0;\n    }\n```\n\n4. to find each valid pair. let me share my intuitive and more complicated idea. for divisor A, assume B = k / A, B would also be a divisor. to avoid duplicates, only counting pairs (A < B); and to contain all the possible cases, count every C > B where C = B * some number. I hope my intuitive solution would help with understanding best solutions which is more clean, simple and elegant.\n\n```\nfor (int i = 0; i < n; i++) { \n            int A = gcd[i];\n            int B = k / A;\n            int idx = max(num2idx[B], i);    // I store the idx of each divisor (factor)\n            while (idx < n) {\n                if (gcd[idx] % B == 0) {\n                    if (i == idx) {\n                        res += (long long)cnt[i] * (long long)(cnt[i] - 1) / 2;\n                    } else {\n                        res += (long long)cnt[i] * (long long)cnt[idx];\n                    }\n                }\n                idx++;\n            }\n        }\n```\n
[]