ABC186 E - Throne

解法

求める回数を$x$として条件を数式で表すと

$$S + Kx \equiv 0 \pmod{N} \tag{1}$$

• (a) KとNが互いに素なとき

式変形すると

$$Kx \equiv -S \pmod{N}$$

Kは$\mod{N}$において逆元をもち

$$x \equiv -\frac{S}{K} \pmod{N}$$

• (b) KとNが互いに素ではないとき

(1)式は$S + Kx$がNの倍数だという意味なので

$$S + Kx = mN$$

$gcd(K, N) = g$とおくと
$K = gK', N = gN'$: $K', N'$は互いに素とおけて

$$S + gK'x = mgN' \\ S = mgN' - gK'x$$

よって$S$は$g$の倍数である必要がある、$S$が$g$の倍数でないとき解なし
$S$が$g$の倍数であるとき、$S = gS'$とおけて、

$$S' + K'x = mN'$$

つまり

$$S' + K'x \equiv 0 \pmod{N'}$$

となって、結局(a)のケースに帰着する

最終的な解法としては

1. $g = gcd(N, K)$を求める
2. $S$が$g$で割り切れない場合解なし
3. $S, K, N$を$g$で割る
4. $-\frac{S}{K} \pmod{N}$を求める

となる

この問題の場合、$N$が素数とは限らないので、
逆元計算でフェルマーの小定理ではなく拡張ユークリッドの互除法を使う必要がある

提出コード

https://atcoder.jp/contests/abc186/submissions/20096332