Codeforces Round #511 (Div. 2) C. Enlarge GCD

题解

题目大意 给n个数字 问最少删掉多少个数字能让这些数字的最大公因数增大 最少保留一个数字

先求出n个数字的最大公因数g 类似于筛素数的方法 i从g+1的位置向后找"素数" 处理过的位置标记不在处理 过程中计算有多少个数字能被i整除

AC代码

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAXN = 1.5e7 + 10;
int pri[MAXN], a[MAXN];

int gcd(int a, int b)
{
	if (!b)
		return a;
	return gcd(b, a % b);
}
int main()
{
#ifdef LOCAL
	freopen("C:/input.txt", "r", stdin);
#endif
	int n, g = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int t;
		scanf("%d", &t);
		a[t]++;
		if (!g)
			g = t;
		else
			g = gcd(g, t);
	}
	int ans = n;
	for (int i = g + 1; i < MAXN; i++) //g是最大公因数 从g后面开始找
		if (!pri[i])
		{
			int cnt = 0, j;
			for (j = i; j < MAXN; j += i)
				pri[j] = 1, cnt += a[j];
			ans = min(ans, n - cnt);
		}
	if (ans < n)
		cout << ans << endl;
	else
		cout << -1 << endl;

	return 0;
}