2183：统计可以被 K 整除的下标对数目（2246 分）

力扣第 281 场周赛第 4 题

题目

给你一个下标从 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

相似问题：

• 2198：单因数三元组
• 1497：检查数组对是否可以被 k 整除（1787 分）
• 3164：优质数对的总数 II（1777 分）
• 3162：优质数对的总数 I（1168 分）

分析

遍历所有下标对时间复杂度高。注意到 nums[i] 重要的是和 k 的公共因子，假如将 nums[i] 替换为 nums[i] 和 k 的最大公约数， 那么结果不会改变。

因此可以将 nums 替换后得到一个计数器 ct，注意到 k 的因子最多 $O(\sqrt k)$ 个，那么二重循环即可。

注意当 x 满足 x*x%k==0 时，对应的下标对是 ct[x] * (ct[x]-1)//2 个

解答

1
2
3

def countPairs(self, nums: List[int], k: int) -> int:
    ct = Counter(gcd(num, k) for num in nums)
    return sum(ct[x]*(ct[y]-(x==y)) for x in ct for y in ct if x*y%k==0)//2

116 ms