FC2ブログ
ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » Java »【Java】拡張ユークリッドの互除法

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


 「ユークリッドの互除法」は「自然数 a, b の最大公約数」を求めるものだったが、「拡張ユークリッド互除法」は「ax + by = gcd(a, b) となる a, b の最大公約数を求める」ものになる。簡単な方程式の整数解を求めるのにも使える。


 ググッてみると C言語で書かれている関数で引数が extgcd(a, b, &x, &y) ['&'は参照渡しとなる] となっているものが多いが、Java はプリミティブ型で参照渡しができないので、ループ版(非再帰版)の方は英語版 Wikipedia に載っているように、引数を extgcd(a, b) にして作ってみよう。無理矢理参照渡しのようにするために、要素が1つの配列を用いる方法もあるが、それは再帰版でのサンプルを見て欲しい。ループ版も同じように書き換えることもできるが、3つ以上の係数に対応したいときなどには不便なので、用途によって使い分けても良いかも知れない。

(参考)
ユークリッドの互除法/拡張ユークリッドの互除法
拡張版ユークリッドの互除法
拡張ユークリッドの互除法 (Extended Euclidean Algorithm)
Extended Euclidean algorithm

●拡張ユークリッドの互除法(非再帰版)
/**<h1>拡張ユークリッド互除法</h1>
* <p>ax + by = gcd(a, b) となる a, b の最大公約数と解 x, y を求める。</p>
* @param a : 数値1(>0)
* @param b : 数値2(>0)
* @return<b>int[]</b> : {[0]:gcd, [1]:x, [2]:y}:最大公約数(なし=1 [互いに素])と解 x, y
*/
public static final int[] extgcd(int a, int b) {
int x0 = 1, x1 = 0;
int y0 = 0, y1 = 1;

while (b != 0) {
int q = a / b;
int r = a % b;
int x2 = x0 - q * x1;
int y2 = y0 - q * y1;

a = b; b = r;
x0 = x1; x1 = x2;
y0 = y1; y1 = y2;
}

return new int[]{a, x0, y0};
}


//メインでは...
int a = 12;
int b = 21;
int[] res = extgcd(a, b);
int g = res[0];
int x = res[1];
int y = res[2];
System.out.println("g = " + g + ", x = " + x + ", y = " + y);
System.out.println(a + " * " + x + " + " + b + " * " + y + " = " + g);
int sum = a * x + b * y;
System.out.println(sum == g);

g = 3, x = 2, y = -1
12 * 2 + 21 * -1 = 3
true

 出力の意味は a = 12, b = 21 のときに、12 * 2 + 21 * -1 = 3 [ax + by = gcd(a, b)] となる解 x = 2, y = -1 が存在することを表す。実はこのような解は常に存在するので、このことを利用して解く問題などもある。

 また、最大公約数がないときは 1 となるが、このとき「互いに素」であることがわかる(お互いの共通の因子を持たない)。しばしばこの性質を利用する解法も見かけるので、覚えておいた方が良いだろう。

 もう1つ、再帰でも書いてみよう。冒頭に書いた「無理矢理参照渡しのようにするために要素が1つの配列を用いる方法」の例でもある。表記が複雑になるので、少し不便だが、C言語などからの移植する際の手法の1つとして覚えておくと役に立つこともあるだろう。

●拡張ユークリッドの互除法(再帰版)
/**<h1>拡張ユークリッド互除法</h1>
* <p>ax + by = gcd(a, b) となる a, b の最大公約数と解 x, y を求める。</p>
* @param a : 数値1(>0)
* @param b : 数値2(>0)
* @param x : 解 x (参照渡し用 new int[1] で作る)
* @param y : 解 y (参照渡し用 new int[1] で作る)
* @return<b>int</b> : 最大公約数(なし=1 [互いに素])
*/
public static final int extgcd(final int a, final int b, final int[] x, final int[] y) {
int g = a;
if (b != 0) {
g = extgcd(b, a % b, y, x);
y[0] -= (a / b) * x[0];
} else {
x[0] = 1;
y[0] = 0;
}
return g;
}


//メインでは...
int a = 12;
int b = 21;
int[] x = new int[1]; //参照渡しにするため、要素1個で作る
int[] y = new int[1]; //参照渡しにするため、要素1個で作る
int g = extgcd(a, b, x, y);
System.out.println("g = " + g + ", x = " + x[0] + ", y = " + y[0]);
System.out.println(a + " * " + x[0] + " + " + b + " * " + y[0] + " = " + g);
int sum = a * x[0] + b * y[0];
System.out.println(sum == g);

g = 3, x = 2, y = -1
12 * 2 + 21 * -1 = 3
true

 ループ版と再帰版とで実行速度を比べてみると、差はほとんどないので、どちらを使っても良いだろう。


 せっかくなので、上記の extgcd() を使って練習問題を解いてみよう。

●双六(すごろく) (参考) アリ本 P.108 [解答例は載ってない]
双六(すごろく)があります。マス目には整数が書かれています。マス目は前後に無限に続いており、
0のマス目がスタートで、1のマス目がゴールなのですが、サイコロの目には a, b, -a, -b の4つの整数しかありません。
そのため、a, b の値によってはゴールに辿り着けない場合があります。

 ┌─┬─┬─┬─┬─┬─┬─┬─┬─┐
…│-4│-3│-2│-1│ 0│ 1│ 2│ 3│ 4│…
 └─┴─┴─┴─┴─┴─┴─┴─┴─┘

4つの目をそれぞれ何回出せばゴールに辿り着けますか?
複数解が存在する場合は、どれか1つを出力しなさい。解がなければ -1 を出力しなさい。

制約
・1 <= a, b <= 109

入力
a = 4, b = 11

●拡張ユークリッド互除法での解法
int a = 4;    //入力
int b = 11; //入力

int[] res = extgcd(a, b);
int g = res[0];
int x = res[1];
int y = res[2];

if (g != 1) {
System.out.println(-1);
} else {
String ans = "" + ((x >= 0) ? x : 0);
ans += " " + ((y >= 0) ? y : 0);
ans += " " + ((x < 0) ? -x : 0);
ans += " " + ((y < 0) ? -y : 0);
System.out.println(ans); //答え
}

3 0 0 1

 答えは左から a, b, -a, -b に対応させて、右へ 4(a)×3回、左へ 11(b)×1回 進めば、1 (gcd(a, b)) のマス目(ゴール)に辿り着けることを表している。ちなみに a = 11, b = 4 と入れ替えて試してみると、答えは「0 3 1 0」となり意味は同じとなる。では逆に辿り着けない例はどうなるだろうか。例えば gcd が2となる a, b を与えれば(両方偶数など)、1には辿り着けない。全探索で見つけるまでもなく一瞬で求められるのは非常に有り難い(笑)。





(関連記事)
【Java】3つ以上の最大公約数を求める(ユークリッドの互除法②)
【Java】最大公約数・最小公倍数を求める(ユークリッドの互除法)
【Java】約数を求める
【Java】素因数分解をする


関連記事
スポンサーサイト



category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  約数  練習問題 
tb: 0   cm: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/219-acab451e
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR