pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

http://codeforces.com/contest/703/problem/E

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

解法

1012 以下の約数の個数の最大値は 6720 なので、

  • dp[ pos ][ 約数の id ] := (mincnt, minsum)

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

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

  1. 素因数分解する
  2. $\gcd(ab,K)=\gcd(a,K)\gcd(b,K/\gcd(a,K))$

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

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

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

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


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

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

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