競技プログラミング用 知識集積所

ABC412E - LCM Sequence

最終更新:

Bot(ページ名リンク)

- view
管理者のみ編集可


問題


必要知識

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回もあれば余裕である。

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

解答例


注意点


別解

タグ:

区間篩
ウィキ募集バナー