欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-09 16:16:58
...

 

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);
}