C++ O(N√N) Solution easy to understand with comments and procedure.
\n// My aproach is first store the factors of all used numbers globally \n// Then iterate to the array nums\n// and find the maximum factor of nums[i]\n// which
```\n// My aproach is first store the factors of all used numbers globally \n// Then iterate to the array nums\n// and find the maximum factor of nums[i]\n// which is also a factor of our number k and store it in variable num (Can be easily done by gcd(nums[i], k))\n\n// Then adding all the count of previous numbers \n// who are divisible by k / num\n\n// Example [1, 2, 3, 4 5] k = 2\n\n// In iteration 0 our count = [0, 0, 0, 0, 0, 0] and so on, not necessary for this example\n// nums[0] = 1, gcd(nums[0], k) is 1 so make num = 1\n// now in previous numbers the numbers which are divisible by (k / num = 2) are count[k / num] = 0\n// make ans += 0\n// ans -> 0\n// increase the count of the factors of num[0], so updated count = [0, 1, 0, 0, 0, 0]\n\n// iteration 1\n// num[1] = 2, gcd(num[1], k) is num = 2\n// so count previous numbers which are divisible by (k / num = 1) is count[k / num] = 1\n// ans += count[k / num]\n// ans -> 1\n// update count with factors , count = [0, 2, 1, 0, 0, 0]\n\n// iteration 2\n// num[2] = 3, gcd(num[2], k) is num = 1\n// ans += (count[k / num] = 1)\n// ans -> 2\n// count = [0, 3, 1, 1, 0, 0]\n\n// iteration 3\n// num[3] = 4, gcd(num[3], k) is num = 2\n// ans += (count[k / num] = 1)\n// ans -> 5\n// count = [0, 4, 3, 1, 0, 0]\n\n// iteration 4\n// num[4] = 5, gcd(num[4], k) is num = 1\n// ans += (count[k / num] = 2)\n// ans -> 7\n// count = [0, 5, 3, 1, 0, 1]\n\n// finally return ans = 7\n\n// Global variables to store the factors of a number\n\nvector<int> factors[100001];\nbool check = false;\n\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n//\t\tBefore executing the program, checking whether factors are initialised or not\n\n\t\tif (!check) {\n            check = true;\n            \n            for (int i = 1; i < 100001; i++)\n                for (int j = i; j < 100001; j += i)\n                    factors[j].push_back(i);\n        }\n\t\t\n        int count[100001] = {0};\n        long long ans = 0;\n\t\t\n\t\tfor (int i = 0; i < nums.size(); i++) {\n//         To check what is the maximum factor that can be achived from the number nums[i] that also exist in k.\n\n            int num = __gcd(nums[i], k);\n\t\t\t\n//         Adding all the numbers who are previous to the ith element and are divisibe by k / num.\n\t\t\t\n            ans += count[k / num];\n\t\t\t\n//         Updating the count of all the factors of numbers untill ith index.\n            \n            for (int j = 0; j < factors[nums[i]].size(); j++)\n                count[factors[nums[i]][j]]++;\n        }\n        \n        return ans;\n    }\n};\n```
['C']