【拡張ユークリッドの互除法】ABC340 - F - S = 1
理解に手こずった問題についてアウトプット。
ABC340 F問題: S = 1 (diff 1516)
提出したコード
https://atcoder.jp/contests/abc340/submissions/50541121
整数$${X, Y}$$が与えられる。$${(X, Y) \not = (0,0)}$$
点$${(0, 0), (X,Y),(A,B)}$$を頂点とする三角形の面積が$${1}$$になる点$${A, B}$$を出力してね。
条件を満たす整数$${(A,B)}$$が存在しない場合は -1 を出力してね。
3頂点の座標から三角形の面積を求める
公式がありそうな問題はまず検索。
3点$${(0, 0), (X,Y),(A,B)}$$を頂点とする三角形の面積$${S}$$を求める公式があります。
$$
S = \frac{1}{2}|BX - AY|
$$
$${S = 1}$$となる$${A, B}$$を求めろということなので
$$
|BX - AY| = 2
$$
です。$${X, Y}$$が決まっていて$${A, B}$$を求めるのはなんとなく気持ち悪いので逆にして、$${A, B}$$が決まっているものとして$${X, Y}$$を求めることにします。
いったん$${BX - AY \geq 0}$$として考えて、
$$
BX + (-A)Y = 2
$$
を満たす$${X, Y}$$を求めることを目指します。
拡張ユークリッドの互除法
$$
ax + by = c
$$
この形の方程式を満たす整数$${(x, y)}$$を求めるアルゴリズムが存在し、拡張ユークリッドの互除法といいます。
数学的に詳しいことは他の記事におまかせします。
拡張ユークリッドの互除法は「$${ax + by = gcd(a,b)}$$を満たす整数$${(x, y)}$$が存在する」と言っていますので、$${g = gcd(a,b)}$$として、まず$${ax + by = g}$$について考えます。
ここで$${a}$$を$${b}$$で割った商を$${q}$$、余りを$${r}$$とします。つまり
$$
a = qb + r
$$
です。これを$${ax + by = g}$$の式に代入すると、
$$
(qb + r)x + by = g \\
\hArr (qx + y)b + rx = g
$$
となります。ここで、$${qx + y = x', x = y'}$$とおくと、
$$
(qx + y)b + rx = g \\
\hArr bx' + ry' = g
$$
となり、$${ax + by = g}$$について考えていた問題から$${bx' + ry' = g}$$を考える問題に移り変わりました。
何も解決してないじゃん、と思えますが$${(a, b)}$$に比べて$${(b, r)}$$は数が小さくなっています。これをずーっと繰り返していると最終的に$${r = 0}$$となる瞬間が訪れます。
これがいわゆる普通のユークリッド互除法であり、最大公約数を求めるアルゴリズムです。このとき$${b = g}$$であり、
$$
bx' + ry' = g (b = g, r = 0) \\
\rArr (x', y') = (1, 0)
$$
となります。いま本当に求めたいのは、最初の式における$${(x, y)}$$の値ですが、$${qx + y = x', x = y'}$$の式変形をずっと行ってきているので、最終的に現れた$${(x', y') = (1, 0)}$$から逆算することで最初の式における$${(x, y)}$$の値も判明します。すなわち、
$$
qx + y = x', x = y'\\
\hArr \begin{cases} x = y' \\ y = x' - qx = x' - qy' \end{cases}
$$
の式を使った逆算をくり返します。このアルゴリズムは再帰関数で実装できます。
""" 拡張ユークリッドの互除法 """
def ex_gcd(a, b):
if b == 0:
return 1, 0
q = a // b
r = a % b
x, y = ex_gcd(b, r)
rx = y
ry = x - q * y
return rx, ry
S = 1となる整数解が存在しない条件
いま、$${BX + (-A)Y = 2}$$を満たす$${X, Y}$$を求めようとしていたのでした。
問題文に「答えが存在しないときは -1 を出力しろ」とあります。どういう場合に答えが存在しないのでしょうか。
前節の拡張ユークリッドの互除法を$${(B, -A)}$$について適用することで求まるのは、$${g = gcd(|A|, |B|), A = gA', B = gB'}$$として
$$
BX + (-A)Y = g \\
\hArr gB'X + g(-A')Y = g \\
\hArr g(B'X + (-A')Y) = g \\
\hArr B'X + (-A')Y = 1 \\
$$
を満たす$${(X, Y)}$$です。同様の式変形を解くべき式に当てはめると
$$
BX + (-A)Y = 2 \\
\hArr gB'X + g(-A')Y = 2 \\
\hArr g(B'X + (-A')Y) = 2 \\
\hArr B'X + (-A')Y = 1 \times \frac{2}{g}
$$
となります。$${(整数) \times (整数) = (整数)}$$であり、$${(整数) + (整数) = (整数)}$$なので、$${B'X + (-A')Y =(整数)}$$かつ$${{\Large\frac{2}{g}} =(整数)}$$、すなわち$${g = 1}$$か$${g = 2}$$でなければなりません。
$${g \geq 3}$$の場合は答えが存在せず、$${g \leq 2}$$の場合は拡張ユークリッドの互除法で求めた整数$${(X, Y)}$$をそれぞれ$${\Large\frac{2}{g}}$$倍したものを答えとします。
""""""
from math import gcd
def ex_gcd(a, b):
if b == 0:
return 1, 0
q = a // b
r = a % b
x, y = ex_gcd(b, r)
rx = y
ry = x - q * y
return rx, ry
A, B = map(int, input().split())
g = gcd(A, B)
if g > 2:
print(-1)
else:
rx, ry = ex_gcd(B, -A)
rx *= 2 // g
ry *= 2 // g
print(rx, ry)
入力例1 に対する出力結果と出力例1 が合致しませんが、複数解のある問題なので仕方ありません。
これが$${-10^{18}\leq X, Y\leq 10^{18}}$$を満たす理由はまだ理解できてないですが、問題は解けました。
【補足】
$$
bx' + ry' = g (b = g, r = 0) \\
\rArr (x', y') = (1, 0)
$$
とした部分について、数学的には$${y'}$$は任意の整数で成り立つような気がします。ただこの問題については$${-10^{18}\leq X, Y\leq 10^{18}}$$の制約があるのでなんでもOKというわけではなさそうです。
試しに$${y' = 2}$$としてもACになりましたが$${y' = 10}$$だとWAになりました。
def ex_gcd(a, b):
if b == 0:
return 1, 2
私の理解している範囲で記事を書いており、数学的に厳密ではない部分もあると思います。ご了承ください。