公式
E - Throne 解説 by en_translator
He can sit on the throne after \(x\) moves if and only if \(S+xK \equiv 0 \bmod N\).
Therefore, it is sufficient to find “the minimum \(x\) such that \(Ax \equiv B \bmod M\).” This problem can be solved in the following way:
- Let \(d = \gcd(A,B,M)\), and replace \(A,B,M\) with \(A/d,B/d,M/d\) respectively.
- If \(\gcd(A,M) \neq 1\), no solution exists.
- If \(\gcd(A,M) = 1\), \(x=A^{-1}B\) is the solution, where \(A^{-1}\) is the inverse of \(A\) modulo \(M\).
The inverse modulo \(M\) can be calculated with extended Euclidean algorithm. (Note that \(A^{M-2}\) is not necessarily the inverse of \(A\) if \(M\) is not a prime)
投稿日時:
最終更新: