本文涉及知识点

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

3312. 查询排序后的最大公约数

给你一个长度为 n 的整数数组 nums 和一个整数数组 queries 。
gcdPairs 表示数组 nums 中所有满足 0 <= i < j < n 的数对 (nums[i], nums[j]) 的 最大公约数 升序 排列构成的数组。
对于每个查询 queries[i] ，你需要找到 gcdPairs 中下标为 queries[i] 的元素。
请你返回一个整数数组 answer ，其中 answer[i] 是 gcdPairs[queries[i]] 的值。
gcd(a, b) 表示 a 和 b 的 最大公约数 。

示例 1：

输入：nums = [2,3,4], queries = [0,2,2]

输出：[1,2,2]

解释：

gcdPairs = [gcd(nums[0], nums[1]), gcd(nums[0], nums[2]), gcd(nums[1], nums[2])] = [1, 2, 1].

升序排序后得到 gcdPairs = [1, 1, 2] 。

所以答案为 [gcdPairs[queries[0]], gcdPairs[queries[1]], gcdPairs[queries[2]]] = [1, 2, 2] 。

示例 2：

输入：nums = [4,4,2,1], queries = [5,3,1,0]

输出：[4,2,1,1]

解释：

gcdPairs 升序排序后得到 [1, 1, 1, 2, 2, 4] 。

示例 3：

输入：nums = [2,2], queries = [0,0]

输出：[2,2]

解释：

gcdPairs = [2] 。

提示：

$2<=n==nums.length<=10^5$
$1<=nums[i]<=5\times 10^4$
$1<=queries.length<=10^5$
0 <= queries[i] < n * (n - 1) / 2

数论 调和级数 容斥原理

M = $\max (nums)$，则gcdParis[i] $\in [1,M]$
cnt1[i]记录，num中i的数量。$i\in [1,M]$
cnt2[i]记录,num中时i的倍数的数的数量。两层循环：一层循环，枚举i；第二层循环，枚举i的倍数，总时间复杂度是O(NlogN)。l
long long cnt3[i]记录最大公约数是：i的数量。
$cnt{3}_i={cnt{2}_i}^2-{\sum }_{j:2}^{i\times j\le M,j是质数}{cnt{2}_{i\times j}}^2$
注意：j是质数，这样就不会重复扣除。
preSum[i] 记录最大公约数$\le i$的数对数量。
auto it = upper(perSum,inx)
–it
it =preSum.begin()便是查询答案。

代码

核心代码

class CCreatePrime {
public:
	CCreatePrime(int iMax):m_isPrime(iMax + 1, true)
	{	
		m_isPrime[0] = m_isPrime[1] = false;
		for (int i = 2; i <= iMax; i++)
		{
			if (m_isPrime[i])
			{
				m_vPrime.emplace_back(i);
			}
			for (const auto& n : m_vPrime)
			{
				if ((long long)n * i > iMax) { break; }
				m_isPrime[n * i] = false;
				if (0 == i % n) { break; }
			}
		}		
	}	
	vector<int> m_vPrime;
	vector<bool> m_isPrime;
};

class Solution {
		public:
			vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
				const int M = *max_element(nums.begin(), nums.end());
				vector<int> cnt1(M + 1);
				for (const auto& i : nums) { cnt1[i]++; }
				vector<long long> cnt2(M + 1), cnt3(M + 1);
				for (int i = 1; i <= M; i++) {
					for (int j = i; j <= M; j += i) {
						cnt2[i] += cnt1[j];
					}
				}
				CCreatePrime cp(M);
				for (int i = M; i >= 1 ; i--) {
					cnt3[i] = cnt2[i] * (cnt2[i] - 1) / 2;
					for (int j = i+i; j <= M;j+=i) {
						cnt3[i] -= cnt3[j];
					}
				}
				vector<long> preSum;
				long long pre = 0;
				for (const auto& i : cnt3) {
					pre += i;
					preSum.emplace_back(pre);
				}
				vector<int> ans;
				for (const auto& ll : queries) {
					auto it = upper_bound(preSum.begin(), preSum.end(), ll);
					ans.emplace_back(it - preSum.begin());
				}
				return ans;
			}
		};

单元测试

vector<int>nums;
		vector<long long> queries;
		TEST_METHOD(TestMethod1)
		{			
			nums = { 2,3,4 }, queries = { 0,2,2 };
			auto res = Solution().gcdValues(nums,queries);
			AssertEx({ 1,2,2 }, res);
		}
		TEST_METHOD(TestMethod2)
		{
			nums = { 4,4,2,1 }, queries = { 5,3,1,0 };
			auto res = Solution().gcdValues(nums, queries);
			AssertEx({ 4,2,1,1 }, res);
		}
		TEST_METHOD(TestMethod3)
		{
			nums = { 2,2 }, queries = { 0,0 };
			auto res = Solution().gcdValues(nums, queries);
			AssertEx({ 2,2 }, res);
		}
		TEST_METHOD(TestMethod4)
		{
			nums = { 10,10 }, queries = {0 };
			auto res = Solution().gcdValues(nums, queries);
			AssertEx({ 10 }, res);
		}
		TEST_METHOD(TestMethod5)
		{
			nums = { 5,10,4 }, queries = { 0 ,1,2};
			auto res = Solution().gcdValues(nums, queries);
			AssertEx({ 1,2,5 }, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。