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

---

問題

ARC197C

必要知識

簡単な内容は省略

• エラトステネスの篩
• Fenwick木（未作成）
• 二分探索（未作成）

考え方

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

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

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

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

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

素数はそれ自身が来た時にしか消えないので、20万番目の素数までに10万個は絶対に残る。
素数定理から、20万番目の素数は20万*ln(20万)でおよそ286万と求められるので、少し余裕をもって300万を上限とすればよい。
なお、実際の20万番目の素数の値は2750159なので、これを調べて上限にしてもよいし、エラトステネスの篩で20万番目を探してもよい。

ただし、これだけではまだa.at(i)の値に小さい数を連打された場合にTLEするので、既出のa.at(i)だった場合にスキップする工夫が必要。

解答例

解答例

注意点

別解

残る数の割合で見積もる。

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万程度。

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

公式解説参照。