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

题目如下
在这里插入图片描述

错误示范:
暴力做法遍历nums数组分别求公约数

using namespace std;
int gcd(int a,int b) {int a1 = a , b1 = b;if(a < b) {a1 = b;b1 = a;}if(a1 % b1 == 0) return b1;return gcd(a1 % b1,b1);}//logn
vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {vector<int> res,ans;for(int i = 0;i < nums.size();i++) {for(int j = i + 1;j < nums.size();j++) {res.push_back(gcd(nums[i],nums[j]));}}sort(res.begin(),res.end());for(long long querie : queries) {ans.push_back(res[querie]);}return ans;
}

时间复杂度(O(n^2 logn))
结果超时
在这里插入图片描述

提示数据集合范围

提示
计算最大公约数为g的个数//所以排除第一个方法
容斥定理

既然要算g的个数就要思考: 什么数对的最大公约数为g?

将 kg(k是正整数)放在一起组成数对一共有n*(n-1)/2种，将数对形成的集合称为q。
这些数对都有公共约数g但是最大公约数不一定是g。(4 8都有约数2 但是最大公约数是4)
因为q中的数对都是k倍的g所以最大公约数必然是r倍的g。(r是正整数)
叠个甲
本人不是数学专业!!!!!以下仅做说明而非严谨证明
设a = kg,b = rg
当k = r 时a = b 最大公约数是a。
当k ≠ r时
现求a 和 b的最大公约数gcd(a,b) 。 
借用百度百科的说法

在这里插入图片描述

a必然能分解成x1 * x2 * x3-----xn * g
b必然能分解成y1 * y2 * y3-----yn * g
所以无论a b是多少倍的g gcd(a,b) = gcd(k,r) * g。
综上所述只要把(wg w>=2)排除掉就是最大公倍数为g的数对数量。

所以通关代码如下。

class Solution {
public:vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {vector<int> ans(queries.size());unordered_map<int,int> map;int max = -1;int n;for(auto num:nums) {if(num > max) max = num;map[num]++;}vector<long long> counter(max + 1);//用于计算最大公约数为g的数量vector<long long > pre(max + 1);for(int i = max;i > 0;i--) {n = map[i];for(int j = 2 * i;j <= max ;j += i) {//从后往前遍历因为wg都已知了直接减就行 从前往后遍历不方便counter[i] -= counter[j];n += map[j];}counter[i] +=  (long long) n * (n - 1)/2;//n都是k倍的g 取两个数组成数对的总数}//前缀和pre[1] = counter[1];for(int i = 2;i < max + 1;i++) {pre[i] = pre[i - 1] + counter[i];}for(int i =0;i<queries.size();i++) {ans[i] = ranges::upper_bound(pre, queries[i]) - pre.begin();}return ans;}
};