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

题意：

给你n个数，然后让你删掉一些数使得剩下的数的gcd比原来的gcd大，并且要使删掉的数的数量最少

最后输出需要删掉的数的数量

 

解析:

大致有两种做法，我用的是将每一个数质因数分解

这个分解用的是线性筛，因为线性筛中遍历到每一个合数时都是通过该合数最小的质因数*某一个数

得到的，那么我们就用mu[]记录每一个数最小的质因数，然后递归地分解这个数就可以了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15000000+10;
const int MAXN = 3e5+10;

bool vis[N];
int mu[N];
int prime[MAXN*5],cnt;
int a[MAXN];
int b[MAXN];
int num[N];
int maxx;
int maxgcd;

inline void solve()
{
    //memset(mu,0,sizeof(mu));
    cnt = 0;
    vis[0]=vis[1]=true;
    for(int i=2; i<N; i++)
    {

        if(!vis[i])   //vis用于标记是否是非素数，若是素数则为false
        {
            prime[cnt++] = i;   //i=d
        }

        for(int j=0; j<cnt&&i*prime[j]<N; j++)
        {
            vis[i*prime[j]] = 1;
            if(i%prime[j]) mu[i*prime[j]] = prime[j];   //如果这个合数(暂且说成合数，质数的情况同理)不能被prime[j]整除,prime[j]肯定不是i的因子(换句话说i中没有与prime[j]相同的因子)
            else    //如果i%prime[j]==0那么i肯定可以分解成prime[j]*(某一个数),这样到之后k=i*prime[j+1]时,k肯定可以从prime[j+1]*(某一个数)*prime[j]得到(一个更大的合数*一个更小的质数得到你)
            {
                mu[i*prime[j]] = prime[j];   //如果这个合数(质数)能被prime[j]整除，那么prime[j]就是i的因子，i*prime[j]中肯定有相同的质因子
                break;         //这样相比与普通筛法O(n*logn*logn)就避免了重复，使得复杂度可以降到O(n)
            }
        }
    }
}

int gcd(int a,int b)
{
    int k;
    while(b)
    {
        k=a%b;
        a=b;
        b=k;
    }
    return a;
}

bool tim[N];
inline void PollardRho(int n)
{
    int flag=0;
    if(!vis[n])
    {
        num[n]++;
        maxx=max(num[n],maxx);
        return;
    }
    int u=n;
    int tmp=mu[u];
    while(vis[u]&&tmp)
    {
        if(!tim[tmp])
        {
            num[tmp]++;
            maxx=max(num[tmp],maxx);
            tim[tmp]=true;
        }
        u=u/tmp;
        tmp=mu[u];
    }
    if(!vis[u]&&!tim[u])
    {
        num[u]++;
        maxx=max(num[u],maxx);
    }
    u=n;
    tmp=mu[u];
    while(vis[u]&&tmp)
    {
        tim[tmp]=false;
        u=u/tmp;
        tmp=mu[u];
    }

}

int main()
{
    solve();
    int n;
    scanf("%d",&n);
    scanf("%d",&a[1]);
    int mg=a[1];
    for(int i=2;i<=n;i++) scanf("%d",&a[i]),mg=gcd(mg,a[i]);
    int flag=0;
    int cm=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        a[i]=a[i]/mg;
        //if(a[i]!=1) flag=1;

    }

    maxx=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==1) continue;
        PollardRho(a[i]);
    }
    if(maxx==0) printf("-1\n");
    else printf("%d\n",n-maxx);
    return 0;
}

另外一种我是看standing里的一位大佬的代码，他是用类似普通筛法(nlogn)枚举每一个公约数的倍数

假如原来的最大公因数是d,那么他从d+1开始枚举每一个数x,然后枚举x的倍数，看a里面有多少数是x的倍数

然后把是x的倍数的数都删掉，因为这些数已经被x替代了，因为一定是x的答案更优，

a里面是x的倍数的数>=a里面是k*x的倍数的数(k=1,2,3,4)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF =0x3f3f3f3f;
const int MAXN =1.5e7 + 10;
int pi[MAXN], a[MAXN];
int main()
{
	int n, d = 0;
	 scanf("%d",&n);
	for (int i=0; i<n; ++i)
	{
		int in;
		scanf("%d", &in);
		a[in]++;
		if (d==0)
			d = in;
		else
			d = __gcd(d,in);
	}
	int ans = n;
	for (int i=d + 1;i<MAXN; ++i)
		if (pi[i]==0)
		{
			int cnt = 0;
			for (int j = i; j < MAXN; j += i)
				pi[j] = 1, cnt += a[j];
			ans = min(ans,n-cnt);
		}
	if (ans < n) printf("%d",ans);
	else printf("-1");
	return 0;
}