初めてのCRT入門。

この問題は次のように言い換えられます。
$s, k, n$が与えられたとき、$s + kx \equiv 0 (\bmod n)$となる$x$を答えよ。存在しない場合、$-1$を答えよ。

CRTを使います。CRTは、ある数$a$を考えたときに、$b_1, b_2, m_1, m_2$を与えることで(これは、2つでなくて複数個与えることもできます)
$$a \equiv b_1 (\bmod m_1) \\
a \equiv b_2 (\bmod m_2)
$$となるすべての$a$および、$\bmod m$を求めます。ここで、今回の問題について次の２式を考えます。

• $kx \equiv 0 (\bmod k) $: これはひどく当たり前の式ですが、１つ目の式として考えます。$k$が整数であることから明らかです。
• $kx \equiv (n-s) (\bmod n) $: まず、$s + kx \equiv 0 (\bmod n) $がもとめたかった式であることを思い出します。ここで、$s$を右辺に移し、$kx \equiv - s (\bmod n) $となります。定義より、$kx \equiv n - s (\bmod n) $となります。言葉でいえば、$kx$の$mod n$をとると$n-s$になるもの。なので、つまり、最初の座席から王座に到達できるだけ(modの世界で)動ける$kx$になります。

ということで、
$$
kx \equiv 0 (\bmod k) \\
kx \equiv (n-s) (\bmod n)
$$
をCRTして$a,m$を得ればよいです。ここで、$a$と$m$の扱いですが、$a$を答えとすればよいです。もしこれが、最初の最小の値ではなくて、$c$回目に座る回数なら、$a + (c-1)m$を答えればよいです。

実装

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y
# https://qiita.com/drken/items/ae02240cd1f8edfc86fd
# a = b1 (mod m1)
# a = b2 (mod m2)
# となるような、 a = r (mod m) を返す
# m=-1のとき解なし。
def crt(bList, mList):
    r, m = 0, 1
    for i in range(len(bList)):
        d, x, y = egcd(m, mList[i])
        if (bList[i] - r) % d != 0:
            return [0, -1]
        tmp = (bList[i] - r) // d * x % (mList[i] // d)
        r += m * tmp
        m *= mList[i] // d
    return [r, m]

for _ in range(int(input())):
    n,s,k = map(int, input().split())
    r, m = crt([0, n-s], [k, n])
    if m == -1:
        print(-1)
    else:
        print(r // k)