Codeforces Round #757 (Div. 2)

　D1まで四完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #757 (Div. 2)
B 0,1,-1,2,-2……と使っていく。
C 区間&の双対セグ木で一個決めて、あとは桁ごとにやるいつもの。
D1 各数の倍数が何個ずつ出現するか計算。あとはDP[i]でiを使うときの最大値でDP。約数列挙に時間を食われた。

— titia (@titia_til) November 26, 2021

D2. Divan and Kostomuksha (hard version)

　やり方はD1と同じ。（自分のツイートだけじゃ解法を理解するのは無理だろうけど、今回は省略）

　問題は約数列挙を高速にできるか？　というところ。

　エラトステネスの篩を使えば高速にできるだろう、とは思っていたけど、良い書き方が分かっておらず、一旦素因数分解してから約数を求めるという二度手間で書いていた。

　実際は、素因数分解を経由せずに書けて、その方が速い（その書き方に気付いておらず、他の方の提出を見て気付いた）。そのように書き直したらPyPyでもACできた。