https://leetcode.com/problems/count-array-pairs-divisible-by-k/
要想的更清楚一些，抓住gcd的性质

个人解答

  1. class Solution:
  2.     def countPairs(self, nums: List[int], k: int) -> int:
  3.         c = Counter([math.gcd(x, k) for x in nums])
  4.         res = 0
  5.         for x in c:
  6.             for y in c:
  7.                 if x * y % k == 0 and x <= y:
  8.                     if x < y:
  9.                         res += c[x] * c[y]
  10.                     else:
  11.                         res += c[x] * (c[x] - 1) // 2
  12.         return res

题目分析

比较容易想到，需要依靠gcd的特性，减少遍历计算的工作量。
一开始的想法是，x * y % k == 0，那么满足条件的x和y，能凑够k的因数即可，所以先找出x与k共有的所有因数，再遍历y来判断：

  1. class Solution:
  2.     def countPairs(self, nums: List[int], k: int) -> int:
  3.         d = {}
  4.         for x in range(2, k + 1):
  5.             if k % x == 0:
  6.                 d[x] = 0
  7.         for n in nums:
  8.             for x in d:
  9.                 if n % x == 0:
  10.                     d[x] += 1
  11.         d[1] = len(nums)
  12.         print(d)
  13.         res = 0
  14.         for n in nums:
  15.             x = k // math.gcd(n, k)
  16.             if n % x == 0:            
  17.                 res += d[x] - 1
  18.             else:
  19.                 res += d[x]
  22.         return res // 2

但其实，只要两个的gcd满足，那么肯定是可以的，所以不用计算所有因数，只要看gcd即可，就像题解中描述的那样。
还是很妙的！