E - Throne 解説 by kyopro_friends


\(x\) 回の行動で玉座に座れることと、\(S+xK \equiv 0 \bmod N\) が成り立つことは同値です。

よって「\(Ax \equiv B \bmod M\) となる最小の \(x\) を求めよ」という形の問題が解ければよいです。この問題は次のように解くことができます。

  1. \(d=\gcd(A,B,M)\) とし、\(A,B,M\) をそれぞれ \(A/d,B/d,M/d\) に置き換える。
  2. \(\gcd(A,M) \neq 1\) のとき解なし
  3. \(\gcd(A,M) = 1\) のとき、\(\bmod M\) における \(A\) の逆元を \(A^{-1}\) として、\(x=A^{-1}B\) が解

\(\bmod M\) における逆元は拡張ユークリッドの互除法などを用いて求めることができます。(\(M\) が素数でない場合、\(A^{M-2}\)\(A\) の逆元になるとは限らないことに注意してください)

投稿日時:
最終更新: