codeforces1047C. Enlarge GCD(思维)

题目链接:codeforces1047C. Enlarge GCD

题意:给定 n 个数,然后这 n 个数的最大公因数是 m ,问最少删除多少个数,可以使剩下的数的最大公因数大于 m 。

题解:

​ 先把 n 个数全部除以 m,剩下的数则全为互质的,用 mp 记录每个 a[i]/m 这个位置的值的个数。

​ 然后用类似于筛素数的方法,枚举质因子,看有多少个数是当前质因子的倍数,取一个最大值,就是能剩下的最多的数量,n-num则为最终答案。

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1.5e7+10;
int n;
int a[300009],mp[maxn];
bool used[maxn];
inline int read()
{
    int num=0,sgn=1;
    char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9'))
        ch=getchar();
    if (ch=='-')
        sgn=-1,ch=getchar();
    while (ch>='0'&&ch<='9')
        num*=10,num+=ch-'0',ch=getchar();
    return num*sgn;
}

int gcd(int x,int y)
{
    if(y==0)
        return x;
    return gcd(y,x%y);
}

int main()
{
    n=read();
    int m=0;
    for(int i=1;    i<=n;   i++)
    {
        a[i]=read();
        m=gcd(a[i],m);
    }
    for(int i=1;    i<=n;   i++)
        mp[a[i]/m]++;
    int ans=0;
    for(int i=2;    i<maxn; i++)
        if(!used[i])
        {
            int temp=0;
            for(int j=i;    j<maxn; j+=i)
            {
                used[j]=1;
                temp+=mp[j];
            }
            ans=max(temp,ans);
        }
    if(ans)
        printf("%d\n",n-ans);
    else
        printf("-1\n");
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。