class Solution {
public:
long long countPairs(vector<int>& nums, int k) {
}
};
2183. 统计可以被 K 整除的下标对数目
给你一个下标从 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 <= 1051 <= nums[i], k <= 105原站题解
java 解法, 执行用时: 233 ms, 内存消耗: 54.5 MB, 提交时间: 2023-07-01 14:14:28
class Solution {
public long countPairs(int[] nums, int k) {
var divisors = new ArrayList<Integer>(); // 预处理 k 的所有因子
for (var d = 1; d * d <= k; d++) {
if (k % d == 0) {
divisors.add(d);
if (d * d < k) divisors.add(k / d);
}
}
var ans = 0L;
var cnt = new HashMap<Integer, Integer>();
for (var v : nums) {
ans += cnt.getOrDefault(k / gcd(v, k), 0);
for (var d : divisors)
if (v % d == 0)
cnt.put(d, cnt.getOrDefault(d, 0) + 1);
}
return ans;
}
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
cpp 解法, 执行用时: 252 ms, 内存消耗: 63.4 MB, 提交时间: 2023-07-01 14:14:17
class Solution {
public:
long long countPairs(vector<int> &nums, int k) {
vector<int> divisors;
for (int d = 1; d * d <= k; ++d) { // 预处理 k 的所有因子
if (k % d == 0) {
divisors.push_back(d);
if (d * d < k) divisors.push_back(k / d);
}
}
long long ans = 0;
unordered_map<int, int> cnt;
for (int v : nums) {
ans += cnt[k / gcd(v, k)];
for (int d : divisors)
if (v % d == 0) ++cnt[d];
}
return ans;
}
};
golang 解法, 执行用时: 204 ms, 内存消耗: 8.5 MB, 提交时间: 2023-07-01 14:14:04
// 统计k的因子
func countPairs(nums []int, k int) (ans int64) {
divisors := []int{}
for d := 1; d*d <= k; d++ { // 预处理 k 的所有因子
if k%d == 0 {
divisors = append(divisors, d)
if d*d < k {
divisors = append(divisors, k/d)
}
}
}
cnt := map[int]int{}
for _, v := range nums {
ans += int64(cnt[k/gcd(v, k)])
for _, d := range divisors {
if v%d == 0 {
cnt[d]++
}
}
}
return
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
golang 解法, 执行用时: 432 ms, 内存消耗: 43.5 MB, 提交时间: 2023-07-01 14:13:46
const mx int = 1e5
var divisors [mx + 1][]int
func init() { // 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5
for i := 1; i <= mx; i++ {
for j := i; j <= mx; j += i {
divisors[j] = append(divisors[j], i)
}
}
}
func countPairs(nums []int, k int) (ans int64) {
cnt := map[int]int{}
for _, v := range nums {
ans += int64(cnt[k/gcd(v, k)])
for _, d := range divisors[v] {
cnt[d]++
}
}
return
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
cpp 解法, 执行用时: 688 ms, 内存消耗: 129.4 MB, 提交时间: 2023-07-01 14:13:32
const int mx = 100001;
vector<int> divisors[mx];
int init = []() { // 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5
for (int i = 1; i < mx; ++i)
for (int j = i; j < mx; j += i)
divisors[j].push_back(i);
return 0;
}();
class Solution {
public:
long long countPairs(vector<int> &nums, int k) {
long long ans = 0;
unordered_map<int, int> cnt;
for (int v : nums) {
ans += cnt[k / gcd(v, k)];
for (int d : divisors[v])
++cnt[d];
}
return ans;
}
};
java 解法, 执行用时: 499 ms, 内存消耗: 96.9 MB, 提交时间: 2023-07-01 14:13:21
class Solution {
final static int mx = 100001;
static ArrayList<ArrayList<Integer>> divisors = new ArrayList<>(mx);
static {
for (var i = 0; i < mx; i++)
divisors.add(new ArrayList<>());
for (var i = 1; i < mx; ++i) // 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5
for (var j = i; j < mx; j += i)
divisors.get(j).add(i);
}
public long countPairs(int[] nums, int k) {
var ans = 0L;
var cnt = new HashMap<Integer, Integer>();
for (var v : nums) {
ans += cnt.getOrDefault(k / gcd(v, k), 0);
for (var d : divisors.get(v))
cnt.put(d, cnt.getOrDefault(d, 0) + 1);
}
return ans;
}
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
python3 解法, 执行用时: 1724 ms, 内存消耗: 55 MB, 提交时间: 2023-07-01 14:13:14
# 统计每个数的因子
MX = 100001
divisors = [[] for _ in range(MX)]
for i in range(1, MX): # 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5
for j in range(i, MX, i):
divisors[j].append(i)
class Solution:
def countPairs(self, nums: List[int], k: int) -> int:
ans = 0
cnt = Counter()
for v in nums:
ans += cnt[k / gcd(v, k)]
for d in divisors[v]:
cnt[d] += 1
return ans