题解 CF1034A 【Enlarge GCD】

· · 题解

\Large\texttt{My Blog}

Description

题目链接：Codeforces 1034A

Mr. F 现在有 n 个正整数 a_i。

他认为这些数的最大公因数太小了，所以他想通过删除其中的一些数来增大这个最大公因数。你的任务是计算出最少的需要删除的数的个数，使得删除之后剩余数的最大公约数大于删除之前的最大公约数。无解输出 -1。

数据范围：2\le n\le 3\times 10^5，1\le a_i\le 1.5\times 10^7

Solution

朴素思路

对于最大公约数，我们可以模拟计算的过程，我们写出所有数字的质因子分解式，对于每个小于 \sqrt{a_i}\approx 4000 的质因子，求出其在 n 个数中最小的指数。

那么要使得 \gcd 增大，必须使得其中一个质因子的指数变大，因此我们对于每个质因子，统计等于最小指数的数的个数，答案即为最小值。

但是我们并没有考虑大于 \sqrt{a_i} 的质因子，由于每个数至多只有一个 >\sqrt {a_i} 的质因子，那么我们统计每个大于 \sqrt{a_i} 的质因子个数，记为 c_i。如果要使得质因子变大，只需要对 n-c_i 取最小值即可（这里的 c_i 必须满足 c_i<n，即 c_i 对原来的最大公约数没有贡献）。

如果 ans 的值为极大值，那么无解。

由于小于 \sqrt{a_i} 的质数个数为 O\left(\frac{\sqrt{a_i}}{\log a_i}\right) 个，分解质因子的复杂度为 O(\log a_i)，故总复杂度为 O(n\sqrt{a_i})。

时间复杂度：O(n\sqrt{a_i})

优化思路

我们发现，如果把 a_i 都除以 \gcd(a_1,a_2,\dots,a_n)，那么此时 \gcd(a_1,a_2,\dots,a_n) 的值就是 1 了，我们的就是使得此时的 a_i 的最大公约数大于 1。

很自然地，我们想到可以枚举 \gcd(a_1,a_2,\dots,a_n)=d，然后统计这些 a_i 中有多少个 d 的倍数即可。

由于质数的个数有 O\left(\frac{a_i}{\log a_i}\right) 个，枚举倍数的复杂度是调和级数，均摊为 O(\log a_i)，那么复杂度为 O(a_i)（计算 \gcd 需要 \log a_i 的复杂度）。

时间复杂度：O(a_i)

Code

朴素思路

#include <cstdio>
#include <cstring>
#include <map>

const int N=3e5+5;
int n,a[N],tot,p[N],mn[N],cnt[N],rcnt[N];
bool flg[N];
std::map<int,int> mp;

void sieve(int n) {
    for(int i=2;i<=n;++i) {
        if(!flg[i]) p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
int getcnt(int &x,int p) {
    int ans=0;
    while(x%p==0) x/=p,++ans;
    return ans;
}
void solve() {
    memset(mn,0x3f,sizeof(mn));
    int idx=0;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=tot;++j) {
            int c=getcnt(a[i],p[j]);
            if(mn[j]>c) mn[j]=c,cnt[j]=1;
            else if(mn[j]==c) ++cnt[j];
        }
        if(a[i]>1) {
            if(!mp[a[i]]) mp[a[i]]=++idx;
            ++rcnt[mp[a[i]]];
        }
    }
    int ans=n;
    for(int i=1;i<=tot;++i) ans=std::min(ans,cnt[i]);
    for(int i=1;i<=idx;++i) ans=std::min(ans,n-rcnt[i]>0?n-rcnt[i]:n);
    printf("%d\n",ans==n?-1:ans);
}
int main() {
    sieve(4000);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    solve();
    return 0;
}

优化思路

#include <cstdio>
#include <algorithm>

const int N=3e5+5,M=1.5e7+5;
int n,tot,a[N],p[M/10],cnt[M];
bool flg[M];

void sieve(int n) {
    for(int i=2;i<=n;++i) {
        if(!flg[i]) p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
int gcd(int x,int y) {
    return y?gcd(y,x%y):x;
}
int main() {
    scanf("%d",&n);
    int d=0,mx=0;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),d=gcd(d,a[i]);
    for(int i=1;i<=n;++i) a[i]/=d,mx=std::max(mx,a[i]),++cnt[a[i]];
    sieve(mx);
    int ans=n;
    for(int i=1;i<=tot;++i) {
        int x=p[i],num=0;
        for(int j=x;j<=mx;j+=x) num+=cnt[j];
        if(num) ans=std::min(ans,n-num);
    }
    printf("%d\n",ans==n?-1:ans);
    return 0;
}