【问题描述】

给定 n 个正整数，a_1,a_2,…,a_n,求最少删去几个数，使得删去后这些数的最大公约数
比原先的所有数的最大公约数大。

【输入】

第一行一个整数 n，第二行 n 个正整数，a_1,a_2,…,a_n。

【输出】

一个数，表示最少删去的个数，若无论怎么删都不会比原来的大，输出-1。

【样例 1】

3
1 2 4

1

【样例 1 解释】

删去 1 这个数，最大公约数从 1 变到 2。

【样例 2】

4
6 9 15 30

2

【样例 2 解释】

删去 6、9，最大公约数从 3 变到 15

【数据范围】

对于 30%的数据，n<=15
对于 50%的数据，n,a_i<=1000
对于 100%的数据，n<=300,000，a_i<=1.5*10^7

思路

首先可以先除掉所有数的gcd,使得问题转化为:选出一个质数,使它的倍数出现的尽可能多
这里使用试乘法
枚举i=1MAX,j=1MAX/i,统计i*j的个数之和,时间复杂度为: $n/1+n/2+…+n/n = n log_n$

代码

#include <bits/stdc++.h>
using namespace std;

int n,a[300005],mt,g,ans,f[15000005];

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

bool IsPrime[15000005];
int Prim[1000000],num;
void euler_prime(int n){  //筛选质数
    int j;
    for(int i=2;i<=n;i++){
        if(!IsPrime[i])
            Prim[++num]=i;
        for(j=1;j<=num;j++){
            if(i*Prim[j]>n)
                break;
            IsPrime[i*Prim[j]]=true;
            if(i%Prim[j]==0)
                break;
        }
    }
}

int main(){
    // freopen("gcd.in","r",stdin);
    // freopen("gcd.out","w",stdout);
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    g=a[1];
    for (int i=1;i<=n;++i) g=gcd(g,a[i]);
    for (int i=1;i<=n;++i) a[i]/=g,mt=max(mt,a[i]);
    for (int i=1;i<=n;++i) f[a[i]]++;
    euler_prime(mt);
    for (int i=1;i<=num;++i){
        int tmp=0;
        for (int j=1;j<=mt/Prim[i];++j){
            tmp+=f[Prim[i]*j];
        }
        ans=max(ans,tmp);
    }
    if (ans==0) cout<<-1<<endl;
    else cout<<n-ans<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/51/