[M数学] lc3164. 优质数对的总数 II(因数分解+倍增+推公式+思维+好题)

1. 题目来源

链接：3164. 优质数对的总数 II

2. 题目解析

挺不错的一道 因数分解、倍增 的题目，需要一定的思维和推公式的能力才能解决。灵神的题解已经非常清晰易懂了，可以直接去看。

倍增思路：

• 枚举 num1、nums2 每个数出现的次数。
• 再枚举 nums2 * k 的倍数，如果在 nums1 中有出现，则基于乘法原理，两个次数相乘累加结果。
• 倍数累计的上界即为 nums1 中的最大值。

分解因数思路：

• 考虑，nums1[i] % (nums2[j] * k) == 0 则有，(nums1[i] / k) % nums2[j] == 0
• 即，nums1[i] 首先是 k 的倍数，且 nums1[i]/k 存在因子 nums2[j]
• 那么可以针对 nums1[i]/k 分解它的各个因子，并记录个数，此时 cnt[a]=b 则等价于有 b 个 nums[i]/k 存在因子 a
• 枚举每一个 nums2，答案累加 cnt[nums2[j]] 即可。

具体的，见灵神题解，很清楚了：

• 两种方法：枚举因子/枚举倍数（Python/Java/C++/Go/JS/Rust）

---

这个东西分析有点难度，见灵神的分析吧…

---

因数分解代码：

class Solution {
public:long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {typedef long long LL;unordered_map<int, int> h;for (auto x : nums1) {if (x % k) continue;x /= k;for (int i = 1; i <= x / i; i ++ ) {if (x % i) continue;h[i] ++ ;if (i * i < x) h[x / i] ++ ;}}LL res = 0;for (int x : nums2) res += h[x];return res;}
};

---

倍增代码：

class Solution {
public:long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {typedef long long LL;unordered_map<int, int> cnt1, cnt2;for (auto x : nums1) if (x % k == 0)cnt1[x / k] ++ ;for (auto x : nums2) cnt2[x] ++ ;int u = -1;for (auto [k, v] : cnt1) u = max(u, k);LL res = 0;for (auto [x, cnt] : cnt2 ) {int s = 0;for (int y = x; y <= u; y += x) s += cnt1[y];res += 1ll * s * cnt;}return res;}
};