初めてのCRT入門。
次のように言い換えられます。
$s, k, n$が与えられたとき、$s + kx \equiv 0 (\bmod n)$となる$x$を答えよ。存在しない場合、$-1$を答えよ。
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$の整数倍を$k$で割った余りは0であることが明らかです。
- $kx \equiv (n-s) (\bmod n) $: 冒頭の式$s + kx \equiv 0 (\bmod n) $から$s$を右辺に移し、$kx \equiv - s (\bmod n) $とします。modの定義より、$kx \equiv n - s (\bmod n) $として良いです。
2つの式を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)