Coprime 2 [AtCoder Beginner Contest 215 D]

https://atcoder.jp/contests/abc215/tasks/abc215_d

解説

https://atcoder.jp/contests/abc215/submissions/25246926

始めてこういう系統の問題を見る人は何から手を付けていいか分からないだろう。
gcdをして1になる数は基本的には互いに素である数となる。
だが、互いに素の数というのは少し列挙するのが厄介で、逆に観点を置いて考えることが競プロでは多いように思う。
（自分的にはですけど）
逆というのは、つまり、gcdをして1にならない数はどういった数であるかを考えてみる。

gcdをして1にならない数は？

gcd(6,k)について考えると、k=2,3,4,6,8,9,10,12みたいな数が1にならない数となる。
何か規則性というか、単純に考えることができないか？
gcdの求め方を中学までさかのぼって思い出してみると、素因数分解していることを思い出す。
6の素因数は2と3であり、それを倍数がkに含まれている。
これで単純に表現できそうだ。

gcd(x,k)!=1であるようなkというのは、xを素因数分解したときの素因数のいずれかの倍数となる。

素因数分解

よって、まずは素因数分解だが、これはO(sqrt(N))でやる方法がある。
ググると以下のようなサイトが見つかったが、他にもサイトがあるかもしれない。
素因数分解-数学アルゴリズム演習ノート-
より高速なアルゴリズムもあるが、O(sqrt(N))でC++なら今回は間に合う。

自分はenumPrimeOnly関数として、少しもじって素因数だけ持ってくるような実装にしている。
以下のng配列を用意する。

ng[x] := gcd(A[i],x)!=1となるiが存在する

すると、取得した素因数pにおいて、ng[p]=trueになる。
これをすべてのA[i]について行っていこう。

倍数について

これで素因数についてはダメなものはマーキングできたが、その倍数について考慮できていない。
このために、ng[p]=trueであれば、ng[2p], ng[3p], ng[4p], ...についてもtrueに変換していく。
実装を見ればやりたいことはだいぶ明らかなのだが、これをp=2から順番にやっていき、間に合うのかが問題。
この各iについて倍数を確認していくループは有名なもので、調和級数的な計算となりO(NlogN)になる。
競技プログラミングにおけるエラトステネスの篩・区間篩・調和級数計算量問題 - はまやんはまやんはまやん

これでngテーブルが完成するので、それを使って後は答えるだけ。

int N, M, A[101010];
bool ng[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N) {
        auto ep = enumPrimeOnly(A[i]);
        fore(p, ep) ng[p] = true;
    }

    rep(p, 2, M) if(ng[p]) {
        for (int y = p + p; y <= M; y += p) ng[y] = true;
    }

    vector<int> ans;
    rep(x, 1, M + 1) if (!ng[x]) ans.push_back(x);

    printf("%d\n", ans.size());
    fore(x, ans) printf("%d\n", x);
}