Enlarge GCD

wjh15101051's space

卧薪尝胆，厚积薄发。

Enlarge GCD

Date: Sat Nov 03 07:06:09 CST 2018

In Category: NoCategory

Description：

给你 $n$ 个数，问至少删掉几个数使得 $\gcd$ 变大。

$1\leqslant n\leqslant 3\times 10^5,1\leqslant a[i]\leqslant 1.5\times 10^7$

Solution：

首先把所有数除以 $\gcd$ ，然后线性筛一下，统计一下每个质数出现了多少次，那么就需要删掉 $n-cnt$ 个数，把答案取个 $\min$ 即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 300010

#define MAX 15000010

bool isprime[MAX];

int prime[MAX],tot = 0;

int mindiv[MAX];

int n;

#define MAXN 300010

int a[MAXN];

int cnt[MAX];

int gcd(int a,int b){return b == 0 ? a : gcd(b,a % b);}

int main()

{

	for(int i = 2;i < MAX;++i)isprime[i] = true;

	for(int i = 2;i < MAX;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			mindiv[i] = i;

		}

		for(int j = 1;j <= tot && i * prime[j] < MAX;++j)

		{

			isprime[i * prime[j]] = false;

			mindiv[i * prime[j]] = prime[j];

			if(i % prime[j] == 0)break;

		}

	}

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	int g = 0;

	for(int i = 1;i <= n;++i)g = gcd(g,a[i]);

	bool tag = true;

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

	{

		if(a[i] != g)

		{

			tag = false;

			break;

		}

	}

	if(tag)

	{

		puts("-1");

		return 0;

	}

	for(int i = 1;i <= n;++i)a[i] /= g;

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

	{

		int s = a[i];

		while(s != 1)

		{

			int k = mindiv[s];

			++cnt[k];

			while(s % k == 0)s /= k;

		}

	}

	int maxv = 0;

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

	{

		maxv = max(maxv,cnt[prime[i]]);

	}

	cout << n - maxv << endl;

	return 0;

}

In tag: 数学-筛法

wjh15101051