本文主要是介绍D. Not Adding，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

D. Not Adding

思路：

我们可以枚举每一个\(1-10^6\)每一个整数，判断它们是否合法，若当前数在数组里面且原数组里面没有任意两个它的倍数的\(gcd\)等于它为不合法的情况。

时间复杂度：\(O(n + maxn\ln(maxn))\)

代码：

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int>q;
unordered_map<int,int>mp;

int main(){
	scanf("%d",&n);
	for(int i = 1; i <= n; i ++ ){
		int x;
		scanf("%d",&x);
		mp[x] = true;
		q.push_back(x);
	}
	int maxn = 1e6;
	int ans = 0;
	for(int i = 1; i <= maxn; i ++ ){//枚举i看是否满足条件
		int cnt = 0, gcd = 0;
		if(mp[i]) continue;
		for(int j = i; j <= maxn; j += i){
			if(mp[j]) {
				cnt ++;
				gcd = __gcd(j, gcd);
			}
			if(cnt >= 2 && gcd == i){
				ans ++;
				break;
			}
		}
	}
	printf("%d",ans);
	return 0;
}

知识点：

调和级数的求和为：

\(\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + .... \frac{1}{n} = \ln(n) + 0.5772157\)

这篇关于D. Not Adding的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！