ABC186 E Throne
Diff 1461.
a = N – S % Nとして, Kx = a(mod N)となるようなaを求める問題. これはKx + Ny = aなる(x,y)の組のうちxが非負整数かつ最小のものを求めることと同値である. まず, あらかじめK,N,aをgcd(K,N,a)で割っておく. そしてこの形の式を解く際は, 拡張ユーグリッドの互除法を用いることができる. 本番はこれで解いた. また, gcdで割ることによりNとKは互いに素になるので単にmod N上で逆元を求めてもよい.