I.枚举因子

枚举因子的核心思想是：如果x可以被d整除，那么一定存在一个x的因子等于d

a[i]能被b[i] * k整除，等价于a[i] / k可以被b整除，枚举a[i] / k 的因子，检索有没有为b中的元素，即可判断是否构成优质数对

算法实现思路如下

1.遍历a，枚举a[i] / k的所有因子，统计到哈希表cnt中。比如遍历完后cnt[3]=5，说明有5个a[i] / k 可以被3整除，等价于有5个a[i]可以被3 * k整除

2.遍历b，把cnt[b[j]]加入答案，即相关因子可以构成优质数对的数量，例如b[j]=3，而cnt[3]=5，即说明了3所对应的相关优质数对有5个，即找到了cnt[3]个优质数对

代码实现如下

class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        unordered_map<int, int> cnt;
        for (int x : nums1) {
            if (x % k) {  //如果无法被k整除，那么就没有计算因子的必要
                continue;
            }
            x /= k;  //等价转换，如上述所言，即优质数对的前一个数
            for (int d = 1; d * d <= x; d++) { // 枚举因子
                if (x % d) {
                    continue;
                }
                cnt[d]++; // 统计因子，即优质数对的后一个数，在x的约束下相关的优质数对的个数
                if (d * d < x) {
                    cnt[x / d]++; // 因子总是成对出现，假设对于6而言，统计cnt[2]等价于统计cnt[3]
                }
            }
        }

        long long ans = 0;
        for (int x : nums2) {
            ans += cnt.contains(x) ? cnt[x] : 0;//利用相关函数直接在b数组里查找存在因子，输出结果
        }
        return ans;
    }
};

II.枚举倍数

即将I的思路逆转过来，例如b[j]=3，枚举3,6,9,12，统计a中有多少个a[i] / k等于3,6,9,12

算法实现思路如下

1.统计a[i] / k 的出现次数，保存到哈希表cnt1中

2.统计b[j]的出现次数(相同的b[j]无需重复计算)，保存到哈希表cnt2中

3.找出cnt1中最大的键值u，即最大值，枚举倍数不可能超过数字本身

4.枚举cnt2中的元素x，然后枚举x的倍数y=x,2x,3x......(不超过u)，累加cnt1[y]，再乘上cnt2[x]，计算答案

代码实现如下

class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        unordered_map<int, int> cnt1; //使用 unordered_map 来存储 nums1 中每个能够被 k 整除的元素的计数。键是元素除以 k 的结果，值是这些结果出现的次数。
        for (int x : nums1) {
            if (x % k == 0) {
                cnt1[x / k]++; //遍历 nums1，如果元素 x 能被 k 整除，就将 x/k 作为键增加到 cnt1 中，并记录其出现次数。
            }
        }
        if (cnt1.empty()) {
            return 0;
        }

        unordered_map<int, int> cnt2;
        for (int x : nums2) {
            cnt2[x]++; //遍历nums2，记录x
        }

        long long ans = 0;
        int u = ranges::max_element(cnt1)->first;//是 cnt1 中最大的键值，表示在 nums1 中能够被 k 整除的所有元素的最大值。

        for (auto& [x, cnt] : cnt2) { //使用范围基 for 循环遍历 cnt2 中的每个元素，x 是 nums2 中的一个元素，而 cnt 是该元素在 nums2 中的出现次数。

            int s = 0;
            for (int y = x; y <= u; y += x) { // 枚举 x 的倍数
                s += cnt1.contains(y) ? cnt1[y] : 0;//对于每一个倍数 y，检查它是否在 cnt1 中存在。如果存在，cnt1[y] 就是 nums1 中能被 k 整除且等于 y 的元素的计数，将其加到 s 中。如果不存在，则不做任何操作（加 0）。
            }
            ans += (long long) s * cnt;//在计算完当前 x 的所有倍数后，将 s 乘以 cnt，这是因为 cnt 是 x 在 nums2 中的出现次数。这样可以得到 nums2 中每个 x 的所有配对数量，并将这些数量累加到 ans 中。
        }
        return ans;
    }
};