AtCoder が提供しているABC（AtCoder Beginner Contest）340 のF問題をC++とPythonで解いてみました。ABC340は、2024年2月10日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 S = 1（Difficulty : 1516）
問題はリンク先をご覧ください。
拡張ユークリッドの互除法を使います。AtCoder Problems による Difficulty は 1516 でした。
解答案
(0, 0)、(A, B), (X, Y) を頂点とする三角形の面積は、
$$\frac{|A X\; – \;B Y|}{2}$$
となります。面積が1となるため、$|A X\; – \;B Y| = 2$ となります。前回に紹介した拡張ユークリッドの互除法を使います。
C++ プログラム例（ABC340F）
自前ライブラリ関数 extgcd を呼び出し不定一次方程式の解を求めます。最大公約数が1となる場合と2になる場合と3以上の場合（解なし）に分けて、解を出力しました。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll extgcd(ll a, ll b, ll& x, ll& y)
{
ll d = a;
if (b != 0) {
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
} else {
x = 1;
y = 0;
}
if (d < 0) {
d = -d;
}
return d;
}
int main()
{
ll x, y;
cin >> x >> y;
ll a, b;
ll d = extgcd(y, -x, a, b);
if (d == 1) {
cout << 2 * a << " " << 2 * b << endl;
} else if (d == 2) {
cout << a << " " << b << endl;
} else {
cout << -1 << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC340F）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 340 F"""
def extgcd(a, b):
d = a
if b != 0:
d, y, x = extgcd(b, a % b)
y -= (a // b) * x
else:
x, y = 1, 0
return (abs(d), x, y)
x, y = map(int, input().split())
d, a, b = extgcd(y, -x)
if d == 1:
print(2 * a, 2 * b)
elif d == 2:
print(a, b)
else:
print(-1)こちらも「AC」と判定されました。
最後に
この問題を調べることによって、不定一次方程式の解き方と、拡張ユークリッドの互除法を学ぶことができました。
引き続き ABC の問題を紹介していきます。
