パナソニックプログラミングコンテスト E - Throne (500)
コンテスト中の考察
何周かしてちょうど王冠にたどり着けば良いので、$ s + kx = nyになる$ x,yが知りたい
変形すると$ ny - kx = sで拡張ユークリッドの互除法で求められる。
求めたいのは最小の正の$ x
nで割った剰余を求めて負だったら$ nを足せば良いのでは? => WA
事前に$ \gcd(n,s,k) = 1なるように全てを割ったらAC
解説の解法
$ s + kx = ny のところから$ kx \equiv -s \mod n
よって$ x \equiv k^{-1}s \mod nになる
$ kの$ \mod nでの逆元は$ kx + ny = 1となる$ xを拡張ユークリッドの互除法で求められる