ARC 101-200/ARC197C - Removal of Multiples - 競技プログラミング用 知識集積所

問題

ARC197C

必要知識

簡単な内容は省略

• エラトステネスの篩（未作成）
• 素因数分解（未作成）
• Fenwick木（未作成）またはsegment木（未作成）
• 二分探索（未作成）

考え方

ある集合に含まれる数のいずれの倍数でもないものを判定するには、エラトステネスの篩と同様に、調べたい数の上限と同じだけのフラグを用意して、倍数のところのフラグを全部消していくことを繰り返せばよい。

ある数以下のところにtrueであるものがいくつあるかはFenwick木かsegment木を使って

• 最初に1以上の全てに1を加える
• フラグを消したときにその位置に-1を加える

とすれば任意のタイミングですぐに取得でき、k本目の旗の探索も二分探索ですぐに解決する。

残るは、「では、調べる個数の上限は？」という問題。

a.at(i)が素数pだった場合、残っている数のうち1/pくらいの割合が消滅する。
つまり、a.at(i)に含まれる全ての種類の素因数pについて重複なく(p-1)/pの積を取れば、全てのa.at(i)と互いに素である数の割合がわかる。
よって、b.at(i)の最大値をその割合で割って、念のため1割増くらいしておけば調べる個数の上限がわかる。
全素数について(p-1)/pの積を考えると、調和級数になるため対数オーダーでの非常に遅い発散となる。
よって、100万個の素数があっても3%くらいは生き残ると思われるので、上限は最大でも300万程度。
したがって、a.at(i)が重複したときにフラグ確認を丸ごとスキップする工夫を足せば、トータルの計算量は最悪でもそのlog(Q)倍くらいと考えられ、制限時間に間に合う。

注意点

別解

上限を20万番目の素数にする。

20万番目の素数である2750159までに10万個は絶対残るので、これを上限に取ることもできる。
コンテスト中に20万番目の素数を求める別プログラムを書く余裕があるかどうかは……。

平方分割（未作成）で解く。

公式解説参照。