Codeforces Round #511 (Div. 2) - C. Enlarge GCD（筛法）

 

http://codeforces.com/contest/1047/problem/C
 

题意：

给你一个数组，让你删去最少的数，使得新数组的gcd>原数组。

 

POINT：

比赛时的做法：（无数的TLE、wa到各种SB错误）

求出原数组的gcd，把原数组的各个元素更新为a[i]/gcd.

这样，在对这个数组进行因式分解。比如45=3*3*5。那么45这个数对于3和5各贡献1次。

质因数被贡献最多的就是删去最少的数，得到的gcd=原gcd*质因数。肯定比原数组大。

分解质因数普通的做法是o(sqrt(x))。所以极端情况是3e5*sqrt(1.5e7) ,肯定超时。

打个素数表，快一点，但还是超时。  在分解质因数的时候直接判断这个数是不是素数，如果是就不用循环下去了。

卡过去了。

 

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define  LL long long
const int N = 3e5+4;
const int M =1000000;
const int maxn = 15000000+33;
int a[N];
int mp[maxn],mp1[maxn];
int num[maxn];
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
int tag[maxn];
int prime[M];
int cnt=0;

void Prime(){
	memset(tag,0,sizeof(tag));
	tag[0]=tag[1]=1;
	for(int i = 2; i<maxn; i++){
		if(!tag[i])
			prime[cnt++]=i;
		for(int j=0;j<cnt && prime[j]*i<maxn; j++){
			tag[i*prime[j]] = 1;
			if(i % prime[j]==0)
				break;
		}
	}
}


int k=0;

void ff(int x)
{
	for(int i=0;i<cnt&&prime[i]<=x;i++){
		if(tag[x]==0) break;
		int j=prime[i];
		if(x%j==0){
			mp1[j]=0;
			while(x%j==0){
				mp1[j]++;
				x/=j;
			}
			num[j]++;
			if(k<num[j]){
				k=num[j];
			}
		}
	}
	if(x>1){
		num[x]++;
		if(k<num[x]){
			k=num[x];
		}
	}
}

int main()
{
	Prime();
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	int x=gcd(a[1],a[2]);
	for(int i=3;i<=n;i++){
		x=gcd(x,a[i]);
	}
	for(int i=1;i<=n;i++){
		ff(a[i]/x);
	}
	if(k==0) printf("-1\n");
	else printf("%d\n",n-k);

}

 

 

还有一种做法比较简单：效率也不差。

还是把原数组更新好。即a[i]=a[i]/gcd。

然后模拟一下素数普通筛的方法。记录每个素数存在于几个数中。O(n*loglog(n)) n=1.5e7。

好像还有线性筛的做法。看不懂。

 

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define  LL long long
const int N = 3e5+4;

const int M = 15000000+33;
int a[N];

int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
int num[M];
int p[M],cnt=0,flag[M];
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int x=a[1];
	for(int i=2;i<=n;i++)
		x=gcd(x,a[i]);
	for(int i=1;i<=n;i++){
		num[a[i]/x]++;
	}
	int ans=0;
	for(int i=2;i<M;i++){
		if(flag[i]==0){
			int cnt=0;
			for(int j=i;j<M;j+=i){
				flag[j]=1;
				cnt+=num[j];
			}
			ans=max(ans,cnt);
		}
	}
	if(ans==0) printf("-1\n");
	else printf("%d\n",n-ans);
}