题目描述
给你一个下标从 0 开始、长度为 n
的整数数组 nums
和一个整数 k
,返回满足下述条件的下标对 (i, j)
的数目:
0 <= i < j <= n - 1
且nums[i] * nums[j]
能被k
整除。
样例
输入: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 整除。
输入:nums = [1,2,3,4], k = 5
输出:0
解释:不存在对应积可以被 5 整除的下标对。
限制
1 <= nums.length <= 10^5
1 <= nums[i], k <= 10^5
算法
(暴力枚举) $O((n + m) \log k)$
- 对于每个数字 $a_i$,求出其与 $k$ 的最大公约数 $g$,所有 $k / g$ 或其 倍数 都可以作为 $a_i$ 的数对。
- 可以定义一个累计数组,$sum(i)$ 表示 $i$ 以及 $i$ 倍数的数字的个数。
- 首先根据原始数组初始化 $sum$,然后对于每个 $i$,遍历其所有倍数,将值累加到 $sum(i)$ 中。
- 最后遍历原数组,累加每个数字 $a_i$ 的数对。但这里需要去掉 $a_i$ 与自身的数对,除此之外,每个数对都被统计了两次,修正后返回即可。
时间复杂度
- 构造 $sum$ 数组的时间复杂度为 $O(m + m/2 + m/4 + \dots + m/k) = O(m \log k)$。其中 $m$ 为最大的可能数字。
- 遍历数组求每个数字与 $k$ 的最大公约数,时间复杂度为 $O(n \log k)$。
- 故总时间复杂度为 $O((n + m) \log k)$。
空间复杂度
- 需要 $O(m)$ 的额外空间存储 $sum$。
C++ 代码
#define LL long long
const int M = 100001;
class Solution {
private:
LL sum[M];
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
public:
LL countPairs(vector<int>& nums, int k) {
memset(sum, 0, sizeof(sum));
for (int x : nums)
sum[x]++;
for (int i = 1; i <= k; i++)
for (int j = i + i; j < M; j += i)
sum[i] += sum[j];
LL ans = 0;
for (int x : nums) {
int g = gcd(x, k);
ans += sum[k / g];
if ((LL)(x) * x % k == 0)
ans--;
}
return ans / 2;
}
};