今天我们看一道 leetcode hard 难度题目：统计可以被 K 整除的下标对数目。
题目
给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ，返回满足下述条件的下标对 (i, j) 的数目：
0 <= i < j <= n - 1且nums[i] * nums[j]能被 k 整除。
示例 1：
代码语言：javascript复制输入：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 整除。
思考
首先想到的是动态规划，一个长度为 n 的数组结果与长度为 n-1 的关系是什么？
首先 n-1 时假设算好了一个结果 result，那么长度为 n 时，新产生的匹配是下标 [0, n-1] 与下标 n 数字的匹配关系，假设这些关系中有 q 个满足题设，则最终答案是 result q。
这种想法适合 (i, j) 满足任意关系的题目，代码如下：
function countPairs(nums: number[], k: number): number {
if (nums.length < 2) {
return 0
}
const dpCache: Record<number, number> = {}
for (let i = 1; i < nums.length; i ) {
switch (i) {
case 1:
if (nums[0] * nums[1] % k === 0) {
dpCache[1] = 1
} else {
dpCache[1] = 0
}
break
default:
// [0,i-1] 洗标范围内与 i 下标组合，看看有多少种可能
let currentCount = 0
for (let j = 0; j <= i - 1; j ) {
if (nums[j] * nums[i] % k === 0) {
currentCount
}
}
dpCache[i] = dpCache[i - 1] currentCount
}
}
return dpCache[nums.length - 1]
};
很可惜超时了，因为回头想想，虽然思路是 dp，但本质上是暴力解法，时间复杂度是 O(n²)。
为了 AC，必须采用更低复杂度的算法。
利用最大公约数解题
如果只循环一次数组，那么必须在循环到数组每一项的时候，就能立刻知道该项与其他哪几项的乘积符合 nums[i] * nums[j] 能被 k 整除，这样的话累加一下就能得到答案。
也就是说，拿到数字 nums[i] 与 k，我们要知道有哪些 nums[j] 是满足要求的。
当然，如果把所有剩余数字循环一遍来找满足条件的 nums[j]，那时间复杂度就还是 O(n²)，但不循环似乎无法继续思考了，这道题很容易在这里陷入僵局。
接下来就要发散思维了，先想这个问题：满足条件的 nums[j] 要满足 nums[i] * nums[j] % k === 0，那除了通过遍历把每一项 nums[j] 拿到真正的算一遍之外，还有什么更快的办法呢？
除了真的算一下之外，想想 nums[j] 还要具备什么特性？这个特性最好和倍数有关，因为如果我们计算所有数字倍数出现的个数，时间复杂度会比较低。
nums[i] 与 k 的最大公约数就满足这个条件，因为我们希望的是 nums[j] * nums[i] 是 k 的倍数，那么 nums[j] 最小的值就是 k / nums[i]，但这个除出来可能不是整数，那必须保证 k 除以的数字是一个整数，这个除数用 nums[i] 与 k 的最大公约数最划算。nums[j] 可以更大，只要是这个结果的倍数就行了，总结一下，nums[j] 要满足是 k / gcd(nums[i], k) 的倍数。
再重点解释下原因，我们假设 nums[i] = 2, k=100，此时是 k 比较大的情况，那么其最大公约数一定小于等于 nums[i]，因此 k / 最大公约数 * nums[j] 得到的数字一定大于 k / nums[i] * nums[j]，毕竟最大公约数比 nums[i] 小嘛，而 k / nums[i] * nums[j] 就是不考虑 nums[j] 是整数情况下让 k 可以整除 nums[i] * nums[j] 时，nums[j] 取的最小值的情况，因此 nums[j] 只要是 k / 最大公约数 的倍数就行了。
反之，如果 k 比 nums[i] 小，比如 nums[i] = 100, k=2，此时最大公约数是小于等于 k 的，但用一个比 k 还要大的 nums[i] 作为乘法的一边，乘出来的结果肯定大于 k，所以不用担心 nums[i] * nums[j] < k 的情况，所以 nums[j] 只要是 k / 最大公约数 的倍数就行了。
综上，无论如何 nums[j] 只要是 k / 最大公约数 的倍数就行了。
所以对于每一个 nums[i]，我们能快速计算出 x = k / gcd(nums[i], k)，接下来只要找到 nums 所有数字中，是 x 倍数的有多少累加起来就行了。这一步也不能鲁莽，因为数组长度非常大，性能更好的方案是：先从1开始到最大值，计算出每个数字的倍数有几个，存在一个 map 表里，之后找倍数有几个直接从 map 表里获取就行了。
比如有数字 1 ~ 10，我们要计算每个数字的倍数出现了几次，大概是这么算的：
- 1,2,3... 数到 10，那么 1 的倍数有 10 个数字。
- 2,4,6,8,10 数 5 次，那么 2 的倍数有 5 个数字。
- 3,6,9 数 3 次，那么 3 的倍数有 3 个数字。
以此类推，我们发现一个规律，即对于长度为 n 的数组，要数的总次数为 n n/2 n/3 ... 1，这是一个调和数列，具体怎么证明的笔者已经忘了，但可以记住它的值趋向于欧拉常数 ln(n 1)，这就是要数的次数，所以用这个方案，整体时间复杂度是 O(nlnn)，比 O(n²) 小了很多。
所以我们只要 “暴力” 的从 1 开始到 nums 最大的数字，把所有数字的倍数都提前计算出来，最后的时间复杂度反而会更小，这是非常神奇的结论。为了避免计算多余的倍数关系，反而时间复杂度是 O(n²)，而暴力计算所有数字倍数的时间复杂度竟然是 O(nlnn)，这个可以背下来。
接下来就简单了，直接上代码。
用 js 实现 gcd（最大公约数）计算可以用辗转相除法：
代码语言：javascript复制function gcd(left: number, right: number) {
return right === 0 ? left : gcd(right ,left % right)
}
整体代码实现：
代码语言：javascript复制function countPairs(nums: number[], k: number): number {
// nums 最大的数字
let max = 0
nums.forEach(num => max = Math.max(num, max))
// Map<数字x, 数字x 倍数在 nums 中出现的次数>
const mutipleMap: Record<number, number> = {}
// 先遍历一次 nums，将其倍数次自增
nums.forEach(num => {
if (mutipleMap[num] === undefined) {
mutipleMap[num] = 1
} else {
mutipleMap[num]
}
})
// 按以下规律数倍数出现的次数，但忽略自身
// 1,2,3...,max
// 2,4,6...,max
// 3,6,9...,max
for (let i = 1; i <= max; i ) {
for (let j = i * 2; j <= max; j =i) {
if (mutipleMap[i] === undefined) {
mutipleMap[i] = 0
}
mutipleMap[i] = mutipleMap[j] ?? 0
}
}
// 答案
let result = 0
// k / gcd(num, k) 的数组出现的次数累加
nums.forEach(num => {
const targetMutiple = k / gcd(num, k)
result = mutipleMap[targetMutiple] ?? 0
})
// 排除自己乘以自己满足条件的情况
nums.forEach(num => {
if (num * num % k === 0) { result-- }
})
return result / 2
};
有几个注意要点。
第一个是 for (let j = i * 2，之所以要乘以 2，是因为在前面遍历 nums 时，自己的倍数已经被算过一次，比如 3,6,9 的 3 已经被初始化算过一次，所以从 3*2=6 开始就行了。
第二个是 mutipleMap[i] = mutipleMap[j]，比如 i=3，j=9 时，因为 9 是 3 的倍数，所以此时 3 的倍数可以继承 9 的倍数的数量，而数字是不断变大的，所以不会重复。
第三个是 if (num * num % k === 0) { result-- }，因为题目要求 0 <= i < j <= n - 1，但我们计算倍数时，比如 9 是 3 的倍数，但 9 可以通过 3 * 3 得到，这种不合规的数据要过滤掉。
第四个是 return result / 2，因为在最后累加次数时，把每个数字与其他数字都判断了一遍，假设 1, 3 是合法的，那么 3, 1 也肯定是合法的，但因为 i < j 的要求，我们要把 3, 1 干掉，所有合法的结果都存在顺序颠倒的 case，所以除以 2.
总结
这道题很容易栽在动态规划超时的坑上面，要解决此题需要跨越两座大山：
- 想到最大公约数与另一个数字之间的关系。
- 意识到暴力计算倍数的时间复杂度是 O(nlnn)。
最后，本题还隐含了 n n/2 n/3 ... 1 为什么极限是 O(nlnn) 的知识，背后有一个 调和数列 的大知识背景，感兴趣的同学可以深入了解。
讨论地址是：精读《算法 - 统计可以被 K 整除的下标对数目》· Issue #495 · dt-fe/weekly
