本文涉及知識點

調和級數
質數、最大公約數、菲蜀定理

LeetCode100321. 優質數對的總數 II

給你兩個整數數組 nums1 和 nums2，長度分別為 n 和 m。同時給你一個正整數 k。
如果 nums1[i] 可以被 nums2[j] * k 整除，則稱數對 (i, j) 為 優質數對（0 <= i <= n - 1, 0 <= j <= m - 1）。
返回 優質數對 的總數。
示例 1：
輸入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1
輸出：5
解釋：
5個優質數對分別是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。
示例 2：
輸入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3
輸出：2
解釋：
2個優質數對分別是 (3, 0) 和 (3, 1)。
提示：
1 <= n, m <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁶
1 <= k <= 10³

調和級數

nums1中的元素如果不是k的倍數，刪除。是k的倍數， /= k。
cnt1 記錄nums1中各元素的數量。
令 max1 = (nums1)
$?$n$\in$nums2。 如果n的m倍(m>0) 在nums1中存在，則是優質對。
如果n$\times$m > max，則無需繼續枚舉m。
枚舉1到y的不超過y的倍數，時間復雜度：y + y/2+y/3 $?$ 1 就是調和級數，故時間復雜度是：O(ylogy)。
注意：如果nums2有重復元素，則時間復雜度是O(nn)。比如：全部是1。所以：必須用cnt2記錄nums2各元素數量。

超時代碼

class Solution {
public:long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {int iMax = *std::max_element(nums1.begin(), nums1.end());vector<int> vCnt1(iMax + 1);for (const auto& n : nums1) {if (0 != n % k) {continue;}vCnt1[n / k]++;}while (vCnt1.size() &&(vCnt1.back() == 0)) {vCnt1.pop_back();}iMax = vCnt1.size() - 1;long long llRet = 0;for (const auto& n : nums2) {for (int tmp = n; tmp <= iMax; tmp += n) {llRet += vCnt1[tmp];}}return llRet;}
};

代碼

class Solution {
public:long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {vector<int> tmp;for (const auto& n : nums1) {if (0 != n % k) { continue; }tmp.emplace_back(n/k);}if (tmp.empty()) { return 0; }int iMax = *std::max_element(tmp.begin(), tmp.end());vector<int> vCnt1(iMax + 1);for (auto& n : tmp) {vCnt1[n]++;}const int iMax2 = *std::max_element(nums2.begin(), nums2.end());vector<long long> vCnt2(iMax2+1);for (auto& n : nums2) {vCnt2[n]++;}long long llRet = 0;for (int i = 1; i <= iMax2; i++ ) {for (int tmp = i; tmp <= iMax; tmp += i) {llRet += vCnt1[tmp]*vCnt2[i];}}return llRet;}
};

擴展閱讀

視頻課程

有效學習：明確的目標 及時的反饋 拉伸區（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

相關下載

想高屋建瓴的學習算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想對大家說的話
《喜缺全書算法冊》以原理、正確性證明、總結為主。
聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。