「Codeforces 1034A」Enlarge GCD

发表于 | | 阅读次数:
字数统计: 1k 字

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

朴素思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
#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;
}

优化思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
#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;
}
0%