Codeforces Round #365 (Div. 2) E. Mishka and Divisors

問題自体は典型だけど TL 1000ms + オーバーフロー + K=1 のコーナーケースで苦しめられた。

10¹² 以下の約数の個数の最大値は 6720 なので、

をして復元すればいい。状態数は 1000 * 6720 である。

状態を遷移させるときに $\gcd(ab,K)$ を計算する必要がある。$a,b\le 10^{12}$ なので $ab$ を計算した時点でオーバーフローしてしまう。対処法は少なくとも 2 つある。

どっちが速いかはケース次第だと思うが、1 つ目の方法はどのような入力に対しても 12 回のループで済むので安心感がある。互除法は最悪 $O(\log_{1.618} n)$ なんだけど実際は結構速く終わるので、さほど気にすることはないかも。

さて、値を計算したら id に変換する必要がある。約数の個数は 6720 なので二分探索の反復回数は 13 回程度である。なので二分探索しても間に合うだろう。

もっと高速化するには、small[10⁶] と large[10⁶] という配列を用意して、small[d[i]]=i, large[K/d[i]]=i としておく。√Kより小さい値は small を参照し、大きい値は large を参照すればいい。これなら O(1) で id を取得できる。

あとは K=1 に気をつけて実装しよう。

452 ms。そこそこ安心感のある実行時間。

互除法 467 ms。こっちの方が実装楽。

前処理が面倒だけど本質的な部分は単純。