LeetCode-Go 题解2183. Count Array Pairs Divisible by KGCD 因子统计 组合计数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 仓库中 2183 题解目录 的解题思路与 Go 实现深入拆解“统计乘积能被 k 整除的下标对”这一经典数论计数问题。你将掌握如何用最大公约数GCD把大规模数组降维成 k 的因子频次表再通过 O(√k) 级别的因子遍历与组合数学完成计数并理解仓库源码中每一行代码的推导依据最终能够独立写出可应对 10^5 级数据量的高效解法。问题定义与约束题目要求见 README 原文给定一个下标从 0 开始、长度为n的整数数组nums和一个整数k返回满足以下两个条件的下标对(i, j)的数目0 i j n - 1nums[i] * nums[j]能被k整除关键约束1 nums.length 10^51 nums[i], k 10^5示例 1Input: nums [1,2,3,4,5], k 2 Output: 7满足乘积能被 2 整除的 7 个下标对为(0,1), (0,3), (1,2), (1,3), (1,4), (2,3), (3,4)对应乘积分别为 2、4、6、8、10、12、20。示例 2Input: nums [1,2,3,4], k 5 Output: 0n最大可达 10^5最坏情况下下标对数量约为 5×10^9 量级因此返回值类型必须使用 64 位整数Go 中为int64同时也决定了不能枚举所有下标对必须寻找数论层面的优化。核心思路用 GCD 把数组降维成因子频次表暴力做法是枚举所有(i, j)并逐一判断nums[i] * nums[j] % k 0时间复杂度 O(n²)在n 10^5时完全不可行。仓库题解给出了一个精妙的降维思路见 README 解题思路先算每个元素与 k 的最大公约数对于每个nums[i]计算g gcd(nums[i], k)。统计这些 gcd 的频次把所有g存入 mapgcds[g]。在因子空间上做两两配对只有gcd(nums[i], k) * gcd(nums[j], k)能被k整除时nums[i] * nums[j]才一定且仅当能被k整除此时(i, j)才是一对合法下标对。为什么可以这样替换设a nums[i]b nums[j]。若a * b % k 0则对任意整数xgcd(x, k)恰好保留了x中与k相关的全部质因子。因此a * b能被k整除当且仅当gcd(a, k) * gcd(b, k)能被k整除。这个等价关系把问题从“原始数值”空间转移到“k 的因子”空间。因子个数的 O(√k) 上界证明题解特别强调循环只需算到 O(√k)因为每个gcd(nums[i], k)一定是k的因子而k的因子总数不超过 O(√k)。简单证明如下假设v是k的一个因子那么k/v也必然是k的因子。v与k/v中必至少有一个小于等于 √k。把每一对互补因子(v, k/v)看成一组k 的全部因子最多可被划分为不超过 √k 组所以因子总数不超过2 * √k O(√k)个。这意味着 map 的 key 集合规模至多为 O(√k)k 10^5时最多几百个即使在其上做两层循环代价也完全可以接受。算法步骤详解整体流程可以划分为三个阶段第一步统计 gcd 频次遍历数组对每个元素计算它与k的最大公约数并计数。仓库源码中直接以int(math.Sqrt(float64(k)))作为 map 的初始容量正好利用了“因子数量不超过 O(√k)”这一结论做容量预分配避免 map 频繁扩容。第二步在因子空间上双层遍历配对枚举 map 中所有 key 对(a, b)若a b直接跳过。这是去重手段保证每个无序下标对只被统计一次只统计一次即可覆盖所有组合因为 map 遍历是无序的必须人为约定遍历顺序。若(a * b) % k ! 0说明这两个 gcd 因子相乘无法被k整除跳过。否则进入第三步进行计数。第三步组合数学计数若a ! b凡是 gcd 等于a的任意元素与 gcd 等于b的任意元素配对都合法下标对数量为n1 * n2n1、n2分别为两个 gcd 的频次。若a b同一 gcd 组内配对相当于从n1个元素中任选 2 个数量为组合数C(n1, 2) n1 * (n1 - 1) / 2。最后把所有计数累加即为答案。仓库源码逐行解析以下是仓库中 2183. Count Array Pairs Divisible by K.go 的完整实现package leetcode import math func countPairs(nums []int, k int) int64 { n : int(math.Sqrt(float64(k))) gcds, res : make(map[int]int, n), 0 for _, num : range nums { gcds[gcd(num, k)] } for a, n1 : range gcds { for b, n2 : range gcds { if a b || (a*b)%k ! 0 { continue } if a ! b { res n1 * n2 } else { // a b res n1 * (n1 - 1) / 2 } } } return int64(res) } func gcd(a, b int) int { for a%b ! 0 { a, b b, a%b } return b }关键点逐一说明make(map[int]int, n)n为√k向下取整用“因子数不超过 2√k”的结论预估容量减少扩容。gcds[gcd(num, k)]单次遍历即完成频次统计时间复杂度 O(n·log k)。双层for a, n1 : range gcds遍历key 集合大小至多 O(√k)内层同样如此所以配对阶段复杂度为 O(√k × √k) O(k)而由于 map 中实际存在的 key 数通常远小于 2√k实际开销更低。if a b || (a*b)%k ! 0 { continue }一行同时完成去重与整除性过滤。a ! b分支与a b分支分别对应“跨组配对”的n1 * n2与“组内配对”的组合数C(n1, 2)是本题计数的核心与 README 代码段 完全一致。最终return int64(res)因为结果可能超过int在 32 位平台上的表示范围最坏约 5×10^9必须显式转为int64。gcd采用欧几里得算法辗转相除法实现当a % b ! 0时不断互换最终返回最大公约数b。复杂度分析时间复杂度统计阶段 O(n·log k)gcd 计算配对阶段 O(T²)其中 T 为 k 的因子数量T ≤ 2√k因此总体为 O(n·log k k)在给定约束n, k 10^5下表现优秀。空间复杂度O(√k)用于存放 gcd 频次 map。测试用例验证仓库配套的 2183. Count Array Pairs Divisible by K_test.go 完整覆盖了题目给出的两个示例countPairs([]int{1, 2, 3, 4, 5}, 2)期望输出7countPairs([]int{1, 2, 3, 4}, 5)期望输出0。测试代码通过结构体question2182组织参数与期望答案在Test_Problem2182中依次打印输入与输出。以示例 1 为例可手工验证算法正确性nums各元素与k2的 gcd 分别为1, 2, 1, 2, 1频次表为{1: 3, 2: 2}因子对(1, 2)乘积为 2 能被 2 整除贡献3 × 2 6因子对(2, 2)组内配对贡献C(2, 2) 1合计6 1 7与期望一致。在仓库根目录go.mod 声明了module github.com/halfrost/LeetCode-GoGo 版本 1.19执行go test即可运行该目录下所有用例go test ./leetcode/2183.Count-Array-Pairs-Divisible-by-K/ -v总结与举一反三本题是“gcd 降维 因子频次 组合计数”的典型代表解题的关键链条可以提炼为将“乘积可整除”的判定等价转化为“gcd 乘积可整除”把问题从原始数值空间投影到 k 的因子空间利用 k 的因子个数不超过 O(√k) 的性质把看似 O(n²) 的配对问题压缩到 O(k) 的因子对遍历使用组合数学分别处理跨组配对n1 × n2与组内配对C(n1, 2)并用a b保证每个无序对只计一次。这一思路同样适用于其他“乘积/和能被某数整除”的计数问题凡是需要统计满足整除性质的二元组都可以优先考虑先求每个元素与 k 的 gcd或取模再利用因子空间的有限性做计数从而避开 O(n²) 的暴力枚举。若读者希望深入该仓库的其他数论与计数类题解可继续浏览 leetcode 目录下对应的题目讲解。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考