leetcode2183 统计可以被 K 整除的下标对数目

思路：

数学题。

实现：

 1 vectorint>> d(100001, vector<int>());
 2 bool init = false;
 3 class Solution
 4 {
 5 public:
 6     long long countPairs(vector<int>& nums, int k)
 7     {
 8         if (!init)
 9         {
10             for (int i = 1; i <= 100000; i++)
11             {
12                 for (int j = i; j <= 100000; j += i)
13                 {
14                     d[j].push_back(i);
15                 }
16             }
17             init = true;
18         }
19         int n = nums.size();
20         unordered_map<int, int> mp;
21         long long res = 0;
22         for (int i = 0; i < n; i++)
23         {
24             int g = __gcd(nums[i], k);
25             int need = k/g; 
26             if (mp.count(need))
27             {
28                 res += mp[need];
29             }
30             for (int j = 0; j < d[nums[i]].size(); j++)
31             {
32                 int div = d[nums[i]][j];
33                 if (!mp.count(div)) mp[div] = 1;
34                 else mp[div]++;
35             }
36         }
37         return res;
38     }
39 };