競技プログラミング用 知識集積所
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つだけは、そういう数じゃなくてもその区間にとっては新しい数である。
それは明らかに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回では全く足りない。
R-Lが10^7まであるので、前処理を除いて1つ平均40回くらいの計算でなんとかしなければならない。
LやRは10^14付近なので、愚直に素因数分解をすると数1つあたりおよそ10^7回の計算が必要になり、40回では全く足りない。
そこで、各数の最小素因数を前処理で求めておくことにする。
すると、単純にその最小素因数の累乗であるかどうかの確認をするだけで済み、平均40回もあれば余裕である。
すると、単純にその最小素因数の累乗であるかどうかの確認をするだけで済み、平均40回もあれば余裕である。