摘要
Title: 2183. 统计可以被 K 整除的下标对数目
Tag: gcd，暴力
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

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

• 题意

  给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ，返回满足下述条件的下标对 (i, j) 的数目：
  0 <= i < j <= n - 1 且
  nums[i] * nums[j] 能被 k 整除。

• 思路

  可能因为k的最大因数个数是常数级别的，所以使第二重循环遍历接近常数
  其实就是将两个数的其中一个数，转化为和k的最小公倍数，也就是k的因子

• 代码

  class Solution:
      def countPairs(self, nums: List[int], k: int) -> int:
          d, res = Counter(), 0
          for num in nums:
              g = gcd(num, k)
              for i in d:
                  if i * g % k == 0:
                      res += d[i]
              d[g] += 1
          return res