かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC186 E - Throne

Baby-step Giant-stepを用いた別解です。

問題はこちら

問題概要

円状に並べられた{N}個の椅子があり，そのうち{1}つは玉座である。玉座の{S}個右にある椅子から始めて，{1}回につき{K}右にある椅子に移動していく行動を繰り返すとき何回目の行動で玉座に移動することができるか．
{T}個のテストケースについて答えよ．

  • {1\leq T\leq 100}
  • {2\leq N\leq 10^9}
  • {1\leq S < N}
  • {1\leq K\leq 10^9}

解説

Baby-step Giant-stepを用いた別解を紹介します．
Baby-step Giant-stepの解説

{f(x)=x+K\bmod{N}}として，{f^{t}(S)=0}となる最小の非負整数{t}を求める問題になります．

{f^{M}(x)=x+KM\bmod{N}}，{f^{-1}(x)=x-K\bmod{N}}であるので，整数集合の値の検索にhashを用い，{M=\lfloor\sqrt{N}\rfloor}とすれば，全体の時間計算量は{O(\sqrt{N})}となります．

提出プログラム

https://atcoder.jp/contests/abc186/submissions/35220724 値の検索にmapを用いているので{O(\sqrt{N}\log{N})}になってます．

感想