拡張ユークリッドの互除法ライブラリを整備する

2回に分けて、一次不定方程式の解き方を紹介しました。

• 一次不定方程式を解く（1）
• 一次不定方程式を解く（2）

学んだ方法をアルゴリズムとして抜き出してライブラリに追加します。

拡張ユークリッドの互除法

一次不定方程式について復習します。一般的に以下が成立します。

互いに素である　$a$ と $b$ が与えられたときに、この方程式の解 $x$ と $y$ は、ユークリッドの互除法と同じ演算を行い。結果が1になるため、式を逆にたどっていけば解が得られます。

「一次不定方程式を解く（1）」で紹介しましたが、$5x + 8y = 1$ の整数解は、以下の手順で求めることができます。

$5$と$8$ は、互いに素です。このため、ユークリッドの互除法を使うと、以下のように差が１となる式が表れます（下から上に読んでください）。

$$3 \; – \; 2 = 1$$

$$5\; – \; 3 = 2$$

$$8 \; – \; 5 = 3$$

この式を逆に組み合わせていきます。

$$3 \;- \; (5\;-\;3) = 1$$

$$(8\;-\;5)\; – \; (5\;-\;(8\;-\;5)) = 1$$

$$-3 \times 5 + 2 \times 8 = 1$$

結果として、$x = -3, y = 2$ を得ることができました。

関数 extgcd として実装する

この考え方を再帰関数 extgcd として表現します。

• long long int 型の変数 a と b を与えると、拡張ユークリッドの互除法に従い、x と y を求める。
• a と b の最大公約数を返す。

実装は「蟻本」（「プログラミングコンテストチャレンジブック」第2版 秋葉拓哉、岩田陽一、北川宣稔著、マイナビ 2012年）を参考にしました。ただし、戻り値は正の数を返すように変更しました。コードは以下となります。

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;
}

ライブラリのテスト

AIZU ONLINE JUDGE で出題されている問題でアルゴリズムをテストします。以下が問題のリンク先です。

NTL 1_E問題 Extended Euclid Algorithm

この問題を解くプログラムは以下です。拡張ユークリッドの互除法の解は、問題にある以下の制約を満たせました。

• |x| ＋|y| が最小値となる x と y が算出される。
• 最小のものが複数ある場合は x $\leqq$ y となるものが算出される。

#include <iostream>

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 a, b, x, y;
	cin >> a >> b;

	(void)extgcd(a, b, x, y);
	
	cout << x << " " << y << endl;

	return 0;
}

最後に

拡張ユークリッドの互除法について整理しました。このライブラリを自分の道具箱に加えることにします。