type
status
date
slug
summary
tags
category
icon
password
题目描述
代码
理解
!! 最妙的点在于，为了求两个数乘积是 k 的倍数，那么把 k 拆成 k = a * b, 然后 nums[i] 是a 的倍数，nums[j] 是 b 的倍数。对于一个固定的 nums[j], nums[i]必须是某一个数 a 的倍数，为了找到尽可能多的 i，那么 a 必须尽可能的小，即 b 必须尽可能的大， 所以 b 应该是 k 和 nums[j] 的最大公因数。
- 这个题比 3164 更难想到一点点，主要难度在于提前储存 k 一共有哪些因子（同样的按一对一对的存储）
- 然后遍历该列表的时候，也有一个非常重要的点，即遍历到某一个点的时候，把这个点之前的所有满足条件的 cnt 的值加到 ans 上，然后再更新 cnt 中的因子数量。
- cnt 统计 nums[j] 前面每个数的每个因子的出现次数（即 nums[i] 中有多少个数包含某个因子），这样对于一个固定的 nums[j]，符合条件的 nums[i] 的个数就是 cnt[k/gcd(k,nums[j])]
- 作者:Lishen Qu
- 链接:https://qulishen.top/article/leetcode-2183
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章