Codeforces Round #511 (Div. 2) C. Enlarge GCD

問題概要

N個の正整数があります。これらの最大公約数を現在より1以上大きくするためには最小でいくつの整数を取り除く必要があるか求めてください。ただし、どのようにしても最大公約数を大きくできない場合は-1を出力してください。

問題のリンク: https://codeforces.com/contest/1047/problem/C

制約

• 2 ≦ N ≦ 3*10⁵
• 0 ≦ a_i ≦ 1.5*10⁷
• Time Limit: 1sec

解法

まず全体の最大公約数を求めておきます。ある数を取り除いたとき最大公約数が現在よりも大きくなるということは残った数には最大公約数の他に共通の約数が存在しているということになります。つまりa_iを最大公約数で割って素因数分解し、最も多くのa_iに共通して含まれる素因数を求めればその個数の差分から取り除くべき個数が求められます。

しかし、この解法はTLEします。素因数分解の計算量はO(√n)なので全体ではO(N√a)となり1secに間に合いません。

実はこの問題はエラトステネスの篩を1回行う過程で解くことができます。

篩が素数の候補を消すとき、ある素数の倍数を消していきます。消される数はもちろんその素数を素因数に持つので消される数にa_iがいくつ含まれているか消しながら数えることでその素因数をもつa_iの個数が高速に求まります。

Code

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

typedef long long ll;
const int MAX_A = int(15e6);
#define REP(i, n) for (int i = 0; i < n; i++)

bool is_prime[MAX_A + 1];
int n, a[MAX_A + 1], amax = 0, g;

int gcd(int p, int q){
    if(p%q == 0) return q;
    else return gcd(q, p%q);
}

int main() {
    scanf("%d",&n);
    int num;
    REP(i,n){
        scanf("%d", &num);
        a[num]++;
        if(i==0) g = num;
        g = gcd(num, g);
        amax = max(amax, num);
    }
    int m = amax/g, ans = n;
    fill(is_prime, is_prime + m + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= m; i++) {
        if (is_prime[i]) {
            int cnt = 0;
            for (int j = i; j*g <= amax; j += i) {
                is_prime[j] = false;
                cnt += a[j*g];
            }
            ans = min(ans, n-cnt);
        }
    }
    cout << (ans < n ? ans : -1) << endl;
    return 0;
}