ABC 401-500/ABC412E - LCM Sequence - 競技プログラミング用 知識集積所

---

問題

ABC412E

必要知識

B以下レベルの内容は省略

• 区間篩（未作成）

考え方

最小公倍数を素因数分解した状態で考えれば、新しい整数が登場するのは「ある素因数pとある自然数kについて、pのk乗を因数に持つ初めての数」のとき。
それは明らかにp^kのときである。
すなわち、2、3、4、5、7、8、9、11、13、16、……、といった、単一素数の累乗のときにA[n]の更新が行われる。
ただし、最初の1つだけは、そういう数じゃなくてもその区間にとっては新しい数である。

さて、問題はそういう数をどうやって高速で探すか。
R-Lが10^7まであるので、前処理を除いて1つ平均40回くらいの計算でなんとかしなければならない。
LやRは10^14付近なので、愚直に素因数分解をすると数1つあたりおよそ10^7回の計算が必要になり、40回では全く足りない。

そこで、各数の最小素因数を前処理で求めておくことにする。
すると、単純にその最小素因数の累乗であるかどうかの確認をするだけで済み、平均40回もあれば余裕である。

各数の最小素因数を求めるには、エラトステネスの篩の応用のところにある内容を区間篩（未作成）で使えばよい。

解答例

解答例

注意点

別解