Hard

题目描述

给你一个下标从 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
解释：
下标对对应的乘积能被 2 整除的共有 7 对：
(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 <= 10^5
  • 1 <= nums[i], k <= 10^5

解题思路

解题思路

核心观察：对于两个数 nums[i] 和 nums[j]，它们的乘积能被 k 整除，当且仅当 nums[i] * nums[j] 包含了 k 的所有质因数且每个质因数的幂次都不小于 k 中对应的幂次。

算法步骤：

  1. 计算需要的因子：对于每个 nums[i]，计算它需要乘以什么数才能被 k 整除。这个数是 k / gcd(k, nums[i])。

  2. 哈希表统计：使用哈希表记录每个"需要因子"的出现次数。

  3. 配对计算：对于当前元素 nums[i]，它的"需要因子"是 need_i = k / gcd(k, nums[i])。我们需要找到之前处理过的元素中，有多少个元素的值能整除 need_i。

  4. 更新统计：处理完当前元素后，将 nums[i] 的所有因子加入哈希表中。

时间优化：通过预处理 k 的因子，我们只需要考虑 k 的因子，大大减少了搜索空间。

代码实现

class Solution {
public:
    long long countPairs(vector<int>& nums, int k) {
        vector<int> divisors;
        for (int i = 1; i * i <= k; i++) {
            if (k % i == 0) {
                divisors.push_back(i);
                if (i != k / i) {
                    divisors.push_back(k / i);
                }
            }
        }
        
        unordered_map<int, int> count;
        long long result = 0;
        
        for (int num : nums) {
            int need = k / __gcd(k, num);
            
            for (int divisor : divisors) {
                if (need % divisor == 0) {
                    result += count[divisor];
                }
            }
            
            for (int divisor : divisors) {
                if (num % divisor == 0) {
                    count[divisor]++;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        import math
        
        # 找到k的所有因子
        divisors = []
        for i in range(1, int(k**0.5) + 1):
            if k % i == 0:
                divisors.append(i)
                if i != k // i:
                    divisors.append(k // i)
        
        count = {}
        result = 0
        
        for num in nums:
            need = k // math.gcd(k, num)
            
            # 检查有多少个之前的数能与当前数配对
            for divisor in divisors:
                if need % divisor == 0:
                    result += count.get(divisor, 0)
            
            # 更新count，添加当前数的所有因子
            for divisor in divisors:
                if num % divisor == 0:
                    count[divisor] = count.get(divisor, 0) + 1
        
        return result

public class Solution {
    public long CountPairs(int[] nums, int k) {
        List<int> divisors = new List<int>();
        for (int i = 1; i * i <= k; i++) {
            if (k % i == 0) {
                divisors.Add(i);
                if (i != k / i) {
                    divisors.Add(k / i);
                }
            }
        }
        
        Dictionary<int, int> count = new Dictionary<int, int>();
        long result = 0;
        
        foreach (int num in nums) {
            int need = k / Gcd(k, num);
            
            foreach (int divisor in divisors) {
                if (need % divisor == 0) {
                    if (count.ContainsKey(divisor)) {
                        result += count[divisor];
                    }
                }
            }
            
            foreach (int divisor in divisors) {
                if (num % divisor == 0) {
                    if (!count.ContainsKey(divisor)) {
                        count[divisor] = 0;
                    }
                    count[divisor]++;
                }
            }
        }
        
        return result;
    }
    
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var countPairs = function(nums, k) {
    function gcd(a, b) {
        while (b) {
            [a, b] = [b, a % b];
        }
        return a;
    }
    
    const gcdMap = new Map();
    
    for (let num of nums) {
        const g = gcd(num, k);
        gcdMap.set(g, (gcdMap.get(g) || 0) + 1);
    }
    
    let count = 0;
    const gcdList = Array.from(gcdMap.keys());
    
    for (let i = 0; i < gcdList.length; i++) {
        for (let j = i; j < gcdList.length; j++) {
            const g1 = gcdList[i];
            const g2 = gcdList[j];
            
            if ((g1 * g2) % k === 0) {
                if (i === j) {
                    const freq = gcdMap.get(g1);
                    count += (freq * (freq - 1)) / 2;
                } else {
                    count += gcdMap.get(g1) * gcdMap.get(g2);
                }
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × d(k))其中 n 是数组长度，d(k) 是 k 的因子个数，通常 d(k) ≤ 2√k
空间复杂度O(d(k))存储 k 的因子和哈希表

相关题目