【拡張ユークリッドの互除法】ABC340 - F - S = 1

igasu_7

2024年3月2日 01:35

理解に手こずった問題についてアウトプット。

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)}$$を求めるアルゴリズムが存在し、拡張ユークリッドの互除法といいます。

数学的に詳しいことは他の記事におまかせします。

$${a,b,c}$$を$${0}$$以外の整数とする。一次不定方程式$${ax+by=c}$$が整数解をもつための必要十分条件は$${c}$$が$${gcd(a,b)}$$で割り切れることである。

Qiita - 拡張ユークリッドの互除法〜一次不定方程式 ax + by = c の解き方〜

拡張ユークリッドの互除法は「$${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}}$$を満たす理由はまだ理解できてないですが、問題は解けました。

【補足】