计算所有数对(i, j)满足条件的方案数
字数 3395 2025-12-23 01:11:36

计算所有数对(i, j)满足条件的方案数

题目描述：给定一个长度为 n 的整数数组 nums 和一个整数 k，计算所有满足以下条件的数对 (i, j) 的个数：

  • 0 ≤ i < j < n
  • nums[i] * nums[j] 能被 k 整除。

注意：如果数组中存在重复元素，不同的下标 (i, j) 即使值相同也被视为不同的数对。
数据范围：n 最大可达 10^5，nums[i] 和 k 最大可达 10^6。

解题思路

这个问题可以直接使用双重循环暴力枚举，时间复杂度为 O(n²)，但 n 最大为 10^5 时无法通过。
我们需要利用 最大公约数（GCD） 的性质来优化。

步骤 1：问题转化

对于数对 (i, j)，要求 nums[i] * nums[j] 能被 k 整除，即：

\[k \mid nums[i] \times nums[j] \]

等价于：

\[\frac{k}{\gcd(k, nums[i])} \mid nums[j] \]

解释：
设 \(d = \gcd(k, nums[i])\)，那么 \(k = d \times m\)，其中 \(m = k/d\)。
由于 nums[i] 已经贡献了因子 \(d\)，那么 nums[j] 必须包含因子 \(m\) 才能让乘积包含完整的 \(k\)。
因此，问题转化为：
对于每个 nums[i]，计算数组中在 i 之后（或之前）的元素中有多少个能被 \(m = \frac{k}{\gcd(k, nums[i])}\) 整除。

步骤 2：高效计算整除数量

我们可以预先计算每个数的倍数出现次数。由于数值范围有限（≤ 10^6），可以先用一个频率数组 freq[x] 记录每个 x 出现的次数。
然后通过 倍数枚举 计算出 cnt_divisible[y]：即能被 y 整除的数组元素的总个数。
具体做法：
对于每个可能的除数 y（从 1 到最大值），枚举 y 的所有倍数 z，将 freq[z] 累加到 cnt_divisible[y] 上。
这样我们可以在 O(M log M) 时间内完成，其中 M 是最大值 10^6。

步骤 3：遍历计算

从左到右遍历数组，对于每个下标 i：

  1. 计算 \(m = k / \gcd(k, nums[i])\)
  2. 我们需要在 i 之后的元素中找到能被 m 整除的数量。
    但是注意，cnt_divisible[m] 包含了整个数组中能被 m 整除的总数，其中包括了 i 之前的元素和 i 自己。
    为了只统计 i 之后的元素，可以这样做：
    • 维护一个当前已经遍历过的元素的频率数组 freq_sofar
    • 对于每个 i，先计算整个数组能被 m 整除的总数 total = cnt_divisible[m]
    • 再计算在 i 之前（包括 i）的元素中能被 m 整除的数量 before
    • 则 i 之后的数量为 total - before
  3. 将 total - before 累加到答案中
  4. 更新 freq_sofar，将 nums[i] 的计数加一，并更新能被 m 整除的“之前计数”

但是上述方法需要动态更新“之前能被 m 整除的数量”，比较麻烦。
更简单的方法是：
我们从左到右遍历，对于每个 i，计算 m，然后我们想知道在 i 之后有多少个元素能被 m 整除。
但“i 之后”不方便直接查询。
我们可以 反向遍历：
从右向左遍历，维护一个频率数组 freq_right 表示当前遍历过的右边元素的频率。
对于每个 i：

  • 计算 m
  • 查询 freq_right 中能被 m 整除的元素总数（需要快速查询）
    但这样每次查询需要 O(M) 时间，不可行。

步骤 4：优化查询

我们需要一种方法，对于给定的 m，快速知道在某个集合（比如右边剩余的元素）中有多少个数能被 m 整除。
这可以通过 预计算每个数的所有因子 来实现：
对于每个数值 v，我们可以预先求出它的所有因子集合。
那么，如果我们有一个频率数组 freq_right 表示右边元素的频率，我们想要知道有多少个右边元素能被 m 整除，等价于：
对 m 的每个倍数 t，累加 freq_right[t]。
但 m 可能很大，枚举倍数较慢。
反过来思考：
如果我们维护 freq_right，那么对于每个右边元素 x，它对哪些 m 有贡献？
它对所有能整除 x 的 m 都有贡献。
所以，如果我们预先求出每个数的所有因子，那么当我们从右边移除一个元素 x 时，我们可以将 x 的所有因子的“右边计数”减一。
这样，对于给定的 m，right_divisible[m] 就是当前右边元素中能被 m 整除的数量，可以在 O(1) 时间内查询。

步骤 5：具体算法流程

  1. 预处理：
    • 计算 max_val = max(max(nums), k)
    • 用筛法或直接枚举，为每个值 v (1 到 max_val) 求出其所有因子列表 factors[v]
  2. 初始化：
    • 数组 freq_right 表示右边元素的频率，初始为整个数组的频率
    • 数组 right_divisible[m] 表示当前右边元素中能被 m 整除的数量，初始为整个数组的对应数量
      可以通过遍历每个数组元素 x，对 x 的每个因子 d，增加 right_divisible[d] 来初始化。
  3. 遍历 i 从 0 到 n-1：
    • 计算 g = gcd(k, nums[i])
    • m = k / g
    • 查询 right_divisible[m]，得到在 i 之后有多少元素能被 m 整除，累加到答案
    • 将当前元素 nums[i] 从右边集合移除：
      对 nums[i] 的每个因子 d，将 right_divisible[d] 减一
      同时更新 freq_right[nums[i]] 减一

步骤 6：时间复杂度

  • 预处理因子：O(M log M)
  • 初始化 right_divisible：遍历每个元素，对其因子更新，每个数的因子个数平均 O(log M)，总 O(n log M)
  • 遍历过程中，每个元素同样更新因子的计数，也是 O(n log M)
  • 查询 O(1)
    总复杂度 O((n + M) log M)，对于 n=10^5, M=10^6 可接受。

步骤 7：举例

nums = [1, 2, 3, 4, 5], k = 6
初始化：整个数组的 right_divisible 计算。
i=0, nums[i]=1, gcd(6,1)=1, m=6/1=6
查询 right_divisible[6]：数组中有多少数能被 6 整除？只有 6 本身，但没有 6，所以为 0。
移除 1：对因子 1 更新计数。

i=1, nums[i]=2, gcd(6,2)=2, m=6/2=3
查询 right_divisible[3]：右边元素 [3,4,5] 中能被 3 整除的有 3 → 1 个
答案加 1
移除 2

i=2, nums[i]=3, gcd(6,3)=3, m=6/3=2
查询 right_divisible[2]：右边元素 [4,5] 中能被 2 整除的有 4 → 1 个
答案加 1
移除 3

i=3, nums[i]=4, gcd(6,4)=2, m=6/2=3
查询 right_divisible[3]：右边元素 [5] 中能被 3 整除的没有 → 0
移除 4

i=4, 右边没有元素，结束。
总答案 = 1 + 1 = 2。
验证：
数对 (1,2): 23=6 整除 6 ✅
数对 (2,3): 34=12 整除 6 ✅
其他不行。

总结

本题的关键是将乘积整除 k 的条件转化为对单个元素的要求，并利用因子预处理和动态计数来高效查询。
通过维护右边元素对每个因子的整除计数，实现 O(1) 查询和 O(log M) 更新，从而在 O((n + M) log M) 时间内解决问题。

计算所有数对(i, j)满足条件的方案数 题目描述：给定一个长度为 n 的整数数组 nums 和一个整数 k ，计算所有满足以下条件的数对 (i, j) 的个数： 0 ≤ i < j < n nums[i] * nums[j] 能被 k 整除。 注意：如果数组中存在重复元素，不同的下标 (i, j) 即使值相同也被视为不同的数对。 数据范围： n 最大可达 10^5， nums[i] 和 k 最大可达 10^6。 解题思路 这个问题可以直接使用双重循环暴力枚举，时间复杂度为 O(n²)，但 n 最大为 10^5 时无法通过。 我们需要利用 最大公约数（GCD） 的性质来优化。 步骤 1：问题转化 对于数对 (i, j)，要求 nums[i] * nums[j] 能被 k 整除，即： \[ k \mid nums[ i] \times nums[ j ] \] 等价于： \[ \frac{k}{\gcd(k, nums[ i])} \mid nums[ j ] \] 解释 ： 设 \( d = \gcd(k, nums[ i ]) \)，那么 \( k = d \times m \)，其中 \( m = k/d \)。 由于 nums[i] 已经贡献了因子 \( d \)，那么 nums[j] 必须包含因子 \( m \) 才能让乘积包含完整的 \( k \)。 因此，问题转化为： 对于每个 nums[i] ，计算数组中在 i 之后（或之前）的元素中有多少个能被 \( m = \frac{k}{\gcd(k, nums[ i ])} \) 整除。 步骤 2：高效计算整除数量 我们可以预先计算每个数的倍数出现次数。由于数值范围有限（≤ 10^6），可以先用一个频率数组 freq[x] 记录每个 x 出现的次数。 然后通过 倍数枚举 计算出 cnt_divisible[y] ：即能被 y 整除的数组元素的总个数。 具体做法： 对于每个可能的除数 y（从 1 到最大值），枚举 y 的所有倍数 z，将 freq[z] 累加到 cnt_divisible[y] 上。 这样我们可以在 O(M log M) 时间内完成，其中 M 是最大值 10^6。 步骤 3：遍历计算 从左到右遍历数组，对于每个下标 i： 计算 \( m = k / \gcd(k, nums[ i ]) \) 我们需要在 i 之后的元素中找到能被 m 整除的数量。 但是注意， cnt_divisible[m] 包含了整个数组中能被 m 整除的总数，其中包括了 i 之前的元素和 i 自己。 为了只统计 i 之后的元素，可以这样做： 维护一个当前已经遍历过的元素的频率数组 freq_sofar 对于每个 i，先计算整个数组能被 m 整除的总数 total = cnt_divisible[m] 再计算在 i 之前（包括 i）的元素中能被 m 整除的数量 before 则 i 之后的数量为 total - before 将 total - before 累加到答案中 更新 freq_sofar ，将 nums[i] 的计数加一，并更新能被 m 整除的“之前计数” 但是上述方法需要动态更新“之前能被 m 整除的数量”，比较麻烦。 更简单的方法是： 我们从左到右遍历，对于每个 i，计算 m，然后我们想知道在 i 之后有多少个元素能被 m 整除。 但“i 之后”不方便直接查询。 我们可以 反向遍历 ： 从右向左遍历，维护一个频率数组 freq_right 表示当前遍历过的右边元素的频率。 对于每个 i： 计算 m 查询 freq_right 中能被 m 整除的元素总数（需要快速查询） 但这样每次查询需要 O(M) 时间，不可行。 步骤 4：优化查询 我们需要一种方法，对于给定的 m，快速知道在某个集合（比如右边剩余的元素）中有多少个数能被 m 整除。 这可以通过 预计算每个数的所有因子 来实现： 对于每个数值 v，我们可以预先求出它的所有因子集合。 那么，如果我们有一个频率数组 freq_right 表示右边元素的频率，我们想要知道有多少个右边元素能被 m 整除，等价于： 对 m 的每个倍数 t，累加 freq_right[t] 。 但 m 可能很大，枚举倍数较慢。 反过来思考： 如果我们维护 freq_right ，那么对于每个右边元素 x，它对哪些 m 有贡献？ 它对所有能整除 x 的 m 都有贡献。 所以，如果我们预先求出每个数的所有因子，那么当我们从右边移除一个元素 x 时，我们可以将 x 的所有因子的“右边计数”减一。 这样，对于给定的 m， right_divisible[m] 就是当前右边元素中能被 m 整除的数量，可以在 O(1) 时间内查询。 步骤 5：具体算法流程 预处理： 计算 max_val = max(max(nums), k) 用筛法或直接枚举，为每个值 v (1 到 max_ val) 求出其所有因子列表 factors[v] 初始化： 数组 freq_right 表示右边元素的频率，初始为整个数组的频率 数组 right_divisible[m] 表示当前右边元素中能被 m 整除的数量，初始为整个数组的对应数量 可以通过遍历每个数组元素 x，对 x 的每个因子 d，增加 right_divisible[d] 来初始化。 遍历 i 从 0 到 n-1： 计算 g = gcd(k, nums[i]) m = k / g 查询 right_divisible[m] ，得到在 i 之后有多少元素能被 m 整除，累加到答案 将当前元素 nums[i] 从右边集合移除： 对 nums[i] 的每个因子 d，将 right_divisible[d] 减一 同时更新 freq_right[nums[i]] 减一 步骤 6：时间复杂度 预处理因子：O(M log M) 初始化 right_divisible ：遍历每个元素，对其因子更新，每个数的因子个数平均 O(log M)，总 O(n log M) 遍历过程中，每个元素同样更新因子的计数，也是 O(n log M) 查询 O(1) 总复杂度 O((n + M) log M)，对于 n=10^5, M=10^6 可接受。 步骤 7：举例 nums = [ 1, 2, 3, 4, 5 ], k = 6 初始化：整个数组的 right_divisible 计算。 i=0, nums[ i ]=1, gcd(6,1)=1, m=6/1=6 查询 right_divisible[6] ：数组中有多少数能被 6 整除？只有 6 本身，但没有 6，所以为 0。 移除 1：对因子 1 更新计数。 i=1, nums[ i ]=2, gcd(6,2)=2, m=6/2=3 查询 right_divisible[3] ：右边元素 [ 3,4,5 ] 中能被 3 整除的有 3 → 1 个 答案加 1 移除 2 i=2, nums[ i ]=3, gcd(6,3)=3, m=6/3=2 查询 right_divisible[2] ：右边元素 [ 4,5 ] 中能被 2 整除的有 4 → 1 个 答案加 1 移除 3 i=3, nums[ i ]=4, gcd(6,4)=2, m=6/2=3 查询 right_divisible[3] ：右边元素 [ 5 ] 中能被 3 整除的没有 → 0 移除 4 i=4, 右边没有元素，结束。 总答案 = 1 + 1 = 2。 验证： 数对 (1,2): 2 3=6 整除 6 ✅ 数对 (2,3): 3 4=12 整除 6 ✅ 其他不行。 总结 本题的关键是将乘积整除 k 的条件转化为对单个元素的要求，并利用因子预处理和动态计数来高效查询。 通过维护右边元素对每个因子的整除计数，实现 O(1) 查询和 O(log M) 更新，从而在 O((n + M) log M) 时间内解决问题。