题解 T93284 【最大公因数】

传送门

30%的做法

• 暴力枚举删掉哪些数即可，复杂度$O(n \log (\max(a_i)) \times 2^n)$

另外20%的做法

• 枚举删掉一些数后的最大公因数$g$，那么不能被$g$整除的数的个数即为要删的数的个数，对结果取$\min$即可

• 复杂度$O(n \times \max(a_i))$

100%的做法

• 首先，用这个序列的$\gcd$去除每个$a_i$，得到一个序列$b_i$

• 序列$b_i$的$\gcd=1$

• 问题转化为最少删掉多少个数使得$b_i$的$\gcd>1$

• 我们删掉一些数以后使得存在一个质数$p$，能整除剩下的所有$b$

• 我们可以统计$b_i$在$[1,10^6]$每个值有多少个点

• 做一次埃筛，在筛的过程中可以顺便统计出每个素数能整除多少个$b_i$

• 我们取能整除最多$b_i$的那个素数即可

• 复杂度与埃筛相同，$O(m \log \log m)$ , $m=\max(a_i)$

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int N=100005, M=1000001;

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

int n, a[N], cnt[M];
bool is[M];

int main()
{
	scanf("%d",&n);
	
	int g = 0;
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		g=gcd(g,a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		a[i]/=g;
 		cnt[a[i]]++;
 	}
	memset(is,1,sizeof(is));
	int ans=N;
	
	for(int i=2;i<M;i++)
		if(is[i])
		{
			int k=cnt[i];
			for(int j=i+i;j<M;j+=i)
			{
				k+=cnt[j];
				is[j]=0;
			}
			ans=min(ans,n-k);
		}
	printf("%d\n",ans);
	return 0;
}