ABC340 F
平面のベクトルの外積は平行四辺形の面積になる(ゲーム制作知識)ことを使うと、2つ目の条件を以下のとおり変形できる
$ \frac{1}{2} |YA - XB| = 1
変形して
$ YA - XB = \pm 2
ここで、$ Y A - XB = -2が解けるなら$ YA - XB = 2も解けるため
$ YA - XB = 2
この形の方程式はベズー方程式と呼ばれ、この式の場合$ 2が$ \gcd(X, Y)で割り切れるときのみ解けることが知られている
取り回しをよくするため、以下のように変形する
$ g = \gcd(X, Y)とする(ただし、$ X < 0のときは$ gに$ -1をかけて$ x > 0となるようにしておく)
$ X = gx
$ Y = gy
$ 2 = gc
こうして、元の式は以下のようになる
$ yA - xB = c
また、$ ya - xb = 1の解を求めれば、$ A = ca, B = cbとできるため、これを解く
$ aについて解く
$ ya = 1 + xb
このとき、$ \bmod xでの解が求まれば、あとは$ bで調整できるため$ \bmod xで考える
$ ya \equiv 1 \pmod{x}
$ a \equiv y^{-1} \pmod{x}
よって$ aが求まった
つぎに$ bを求める
$ xb = ya - 1
ここで$ ya - 1は$ xで割り切れるため
$ b = \frac{ya - 1}{x}
※$ x = 0のときはゼロ除算が発生してしまうが、制約より$ x = 0なら$ y \ne 0なので$ x, yを逆の順番で求めればよい
$ b \equiv -x^{-1} \pmod y, a = \frac{xb + 1}{y}
これで解くことができた
なお、途中結果は$ 10^{36}くらいになるため、オーバーフローに注意
↓疑似コード
code:py
def solve(X, Y):
if X == 0:
B, A = solve(Y, X)
return A, B
g = gcd(X, Y)
if 2 % g != 0: # ベズー方程式が解けないとき
return None, None
if X < 0:
g *= -1
x = X / g
y = Y / g
c = 2 / g
a = inv_mod(y, x)
b = (y * a - 1) / x
A = c * a
B = c * b
return A, B
X, Y = input()
A, B = solve(X, Y)
if A == None or abs(A) > 10**18 or abs(B) > 10**18:
print(-1)
else:
print(A, B)