本文涉及知识点

数论：质数、最大公约数、菲蜀定理

LeetCode3164. 优质数对的总数 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³

调和级数

max1是nums1的最大值,max2是nums2的最大值。 cnt1[nums1[i]]记录nums1[i]出现的次数。 cnt2[nums2[i]]记录nums2[i]出现的次数。
for i = 1 To max2
for( j = ik To j <= max1; j += ik)
ans += cnt2[i] *cnt1[j];
时间复杂度：O(mlogm),m = max(iMax1,iMax2)

代码

核心代码

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;
	}
};

单元测试

vector<int> nums1, nums2;
		int k;
		TEST_METHOD(TestMethod11)
		{
			nums1 = { 1, 3, 4 }, nums2 = { 1, 3, 4 }, k = 1;
			auto res = Solution().numberOfPairs(nums1, nums2, k);
			AssertEx(5LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums1 = { 1,2,4,12 }, nums2 = { 2, 4 }, k = 3;
			auto res = Solution().numberOfPairs(nums1, nums2, k);
			AssertEx(2LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums1 = { 1 }, nums2 = {2 }, k = 2;
			auto res = Solution().numberOfPairs(nums1, nums2, k);
			AssertEx(0LL, res);
		}
		TEST_METHOD(TestMethod14)
		{
			const long long e5 = 100'000;
			nums1.assign(e5,e5), nums2.assign(e5,1), k = 1;
			auto res = Solution().numberOfPairs(nums1, nums2, k);
			AssertEx(e5*e5, res);
		}