Codeforces Round #511 Div.1 A Div.2 C

嗯切一题走人很开心。

gzy-50分比我还惨。

题意：有n个数，去掉尽量少的数使得剩下数的gcd变大。

首先把这n个数都除以gcd，就变成了去掉尽量少的数使得gcd不等于1。

可以枚举一个质数，然后统计这个质数是a数组中多少个数的约数。

线性筛，记录每个数最小的约数，每次除以约数，\(O(n\log a)\)。

Time Limit Exceeded on pretest 8

线性筛的时候顺便记录每个数去掉重复约数之后的数

\(2*3*5*7*11*13*17*19\)，再乘23就炸了

每个数最多8个不同质因数

所以就是\(O(8n)\)的了

#include<bits/stdc++.h>

#define il inline

#define vd void

#define ll long long

il int gi(){

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int pr[1000000],a[15000001],yes[15000001];

int d[15000001],dd[15000001];

int ans[1000000];

main(){

    int n=gi(),g=0;

    for(int i=1;i<=n;++i)a[i]=gi(),g=std::__gcd(g,a[i]);

    for(int i=1;i<=n;++i)a[i]/=g;

    for(int i=2;i<=15000000;++i){

        if(!yes[i])pr[++pr[0]]=i,d[i]=pr[0],dd[i]=i;

        for(int j=1;j<=pr[0]&&1ll*i*pr[j]<=15000000;++j){

            yes[i*pr[j]]=1;

            d[i*pr[j]]=j;dd[i*pr[j]]=dd[i]*pr[j];

            if(i%pr[j]==0){dd[i*pr[j]]=dd[i];break;}

        }

    }

    dd[1]=1;

    int Ans=0;

    for(int i=1;i<=n;++i){

        a[i]=dd[a[i]];

        while(a[i]!=1)++ans[d[a[i]]],a[i]/=pr[d[a[i]]];

    }

    for(int i=1;i<=pr[0];++i)Ans=std::max(Ans,ans[i]);

    Ans=n-Ans;

    if(Ans==n)Ans=-1;

    printf("%d\n",Ans);

    return 0;

}

巴特西

Codeforces Round #511 Div.1 A Div.2 C

最新文章

热门文章