Codeforces Round #766 (Div. 2)

GCD + 调和级数

题意

有 \(n\;(1<=n<=10^6)\) 个互不相同的数 \(a[i]\;(1<=a[i]<=10^6)\), 每次可以在 a 数组中选择两个数 \(a[i],a[j]\), 将令 \(d=gcd(a[i],a[j])\), 如果 \(d\), 不在 a 数组中，就把 \(d\) 加进去

求最多能加进去多少个数

思路

看到值域只有 \(10^6\), 可以想到可能与调和级数有关
对于数论题，很多时候可以更换枚举的顺序，所以可以枚举 \(d\), 看 \(d\) 能不能被加进去
对于所有 \(d\) 的倍数，如果他们的 \(gcd\) 等于 \(d\), 说明 \(d\), 可以被加进去

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <cmath>

#include <set>

using namespace std;

#define endl "\n"

typedef long long ll;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n;

int cnt[N];

int main()

{

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;

	int ans = 0;

	for (int i = 1; i <= n; i++)

	{

		int x;

		cin >> x;

		cnt[x]++;

	}

	for (int d = 1; d <= N - 10; d++)

	{

		int g = 0;

		for (int i = d; i <= N - 10; i += d)

			if (cnt[i]) g = __gcd(g, i);

		if (g == d && !cnt[d]) ans++;

	}

	cout << ans << endl;

    return 0;

}

巴特西

Codeforces Round #766 (Div. 2) - D. Not Adding

GCD + 调和级数

题意

思路

最新文章

热门文章