【最大公约数 调和级数】2183.统计可以被 K 整除的下标对数目

class Solution {
public:
  long long countPairs(vector<int>& nums, int k) {
    const int iMax = *std::max_element(nums.begin(), nums.end());
    vector<int> cnt(iMax + 1);
    for (const auto& n : nums) {
      cnt[n]++;
    }
    vector<int> cnt2(k + 1);
    for (int i = 1; i <= k; i++) {
      for (int x = i; x <= iMax; x += i) {
        cnt2[i] += cnt[x];
      }
    }
    long long llRet = 0;
    for (const auto& n : nums) {
      llRet += cnt2[k / gcd(n, k)];
      if (((long long)n * n >= k) && (0 == (long long)n * n % k)) {
        llRet --;
      }
    }
    return llRet / 2;
  }
};

template<class T>
void Assert(const T& t1, const T& t2)
{
    assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
    if (v1.size() != v2.size())
    {
        assert(false);
        return;
    }
    for (int i = 0; i < v1.size(); i++)
    {
        Assert(v1[i], v2[i]);
    }
}
int main()
{
  vector<int> nums;
  int k;
  {
    Solution sln;
    nums = { 2,2,10 }, k = 4;
    auto res = sln.countPairs(nums, k);
    Assert(3LL, res);
  }
  {
    Solution sln;
    nums = { 1,2,3,4,5 },k=2;
    auto res = sln.countPairs(nums,k);
    Assert(7LL, res);
  }
  {
    Solution sln;
    nums = { 1,2,3,4 }, k = 5;
    auto res = sln.countPairs(nums, k);
    Assert(0LL, res);
  }
}