题目

给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ，返回满足下述条件的下标对 (i, j) 的数目：

0 <= i < j <= n - 1 且 nums[i] * nums[j] 能被 k 整除。

示例 1：输入：nums = [1,2,3,4,5], k = 2 输出：7

解释：共有 7 对下标的对应积可以被 2 整除：

(0, 1)、(0, 3)、(1, 2)、(1, 3)、(1, 4)、(2, 3) 和 (3, 4)

它们的积分别是 2、4、6、8、10、12 和 20 。

其他下标对，例如 (0, 2) 和 (2, 4) 的乘积分别是 3 和 15 ，都无法被 2 整除。

示例 2：输入：nums = [1,2,3,4], k = 5 输出：0

解释：不存在对应积可以被 5 整除的下标对。

提示：1 <= nums.length <= 105

1 <= nums[i], k <= 105

解题思路分析

1、数学-最大公约数；时间复杂度O(nlog(n))，空间复杂度O(log(n))

func countPairs(nums []int, k int) int64 {   res := int64(0)   m := make(map[int]int)   for i := 0; i < len(nums); i++ {      m[gcd(k, nums[i])]++ // k和nums[i]的最大公约数   }   for k1, v1 := range m {      for k2, v2 := range m {         // 核心：a*b是k的倍数 => gcd(a,k)*gcd(b,k)是k的倍数         if k1*k2%k == 0 {            res = res + int64(v1)*int64(v2) // 组合数         }      }   }   for i := 0; i < len(nums); i++ {      if nums[i]*nums[i]%k == 0 { // 本身x本身：不满足要求         res--      }   }   return res / 2 // 要满足有序要求}func gcd(a, b int) int {   for a != 0 {      a, b = b%a, a   }   return b}

2、数学-最大公约数；时间复杂度O(nlog(n))，空间复杂度O(log(n))

func countPairs(nums []int, k int) int64 {   res := int64(0)   m := make(map[int]int)   for i := 0; i < len(nums); i++ {      m[gcd(k, nums[i])]++ // k和nums[i]的最大公约数   }   for k1, v1 := range m {      for k2, v2 := range m {         // 核心：a*b是k的倍数 => gcd(a,k)*gcd(b,k)是k的倍数         if k1*k2%k == 0 {            if k1 < k2 {               res = res + int64(v1)*int64(v2)            } else if k1 == k2 {               res = res + int64(v1)*int64(v1-1)/2            }         }      }   }   return res}func gcd(a, b int) int {   for a != 0 {      a, b = b%a, a   }   return b}

Hard题目，核心思路是a*b是k的倍数 => gcd(a,k)*gcd(b,k)是k的倍数