【Codeforces 1034A】Enlarge GCD

题意

【题解】

设原来n个数字的gcd为g
减少某些数字之后
新的gcd肯定是g的倍数
即g*x
我们可以枚举这个x值(x>=2)
看看原来的数字里面有多少个是g*x的倍数就可以了
(开个数组_cnd[i]表示数字i有多少个)
为了方便起见
可以先把每个数字a[i]都除g
这样的话相当于在原数组中找到一个大于等于2的数字x
然后新的a[]数组中能被x整除的数字尽可能多(需要删掉的就越少)
这里x只要枚举素数p就好了。
因为如果x是p的倍数的话,能被x整除的数字肯定也都能被p整除,如果x是最后的gcd也没事
枚举p的时候肯定也能得到这个x对应的答案(虽然此时p不一定是最后的gcd)

有个性质,n以内素数的个数约等于n/log(n)

然后如果枚举1..n每个数的倍数的话

复杂度是nlogn

即(n/1+n/2+n/3+....)=n(1/1+1/2+1/3+...+1/n)

≈nlogn

那么平均每个数字需要logn的复杂度

而只要枚举素数,

所以复杂度就为n/lognlogn->趋近于O(n)

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5;

const long long M = 15e6;

int n;

int a[N+10],g;

int ssb[M+10],cnt;

bool eul[M+10];

int _cnt[M+10];

int main(){

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n;

    for (int i = 1;i <= n;i++) cin >> a[i];

    g = a[1];

    for (int i = 2;i <= n;i++) g = __gcd(g,a[i]);

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

        a[i]/=g;

        _cnt[a[i]]++;

    }

    for (int i = 2;i <= M;i++)

        if (!eul[i]){

            ssb[++cnt] = i;

            for (int j = 1;j <= cnt;j++){

                if (ssb[j]*i>M) break;

                eul[ssb[j]*i] = true;

                if (i%ssb[j]==0) break;

            }

        }

    int ans = -1;

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

        int temp = 0;

        int p = ssb[i];

        for (int j = p;j<=M;j+=p){

            temp+=_cnt[j];

        }

        int need = n-temp;

        if (need==n) continue;

        if (ans==-1){

            ans = need;

        }else{

            ans = min(ans,need);

        }

    }

    cout<<ans<<endl;

	return 0;

}

巴特西

【Codeforces 1034A】Enlarge GCD

最新文章

热门文章